Ant Colony System for a Problem in Reverse Logistic
Franklin JOHNSON1, Jorge VEGA2, Guillermo CABRERA3*, Enrique CABRERA4
1 Universidad de Playa Ancha, Chile
2 Universidad de Antofagasta,
Department of Electrical Engineering, Chile
3 Pontificia Universidad Católica de Valparaíso, Chile
4 Universidad de Valparaíso, CIMFAV, Chile
* Corresponding author
Abstract: Distribution, redistribution, recycling and repacking have become an important issue in logistic planning duringthe last decades. While keeping operational cost as low as possible still the main goal for logistic planners, other aspectssuch as recycling are getting more attention from industry. In this article the well known Ant Colony System (ACS), a bioinspiredalgorithm, is implemented to solve a problem arising in Reverse Logistic namely Vehicle Routing Problem withSimultaneous Delivery and Pickup (VRPSDP). To solve this problem we need to find the optimal set of paths that meet, atthe same time, customer delivery and pickup demands. In order to solve this problem, our ACS implementation makes useof a strategy that mimics the effect of the pheromone in the natural Ants behaviour. To do that, each vehicle is viewed asan individual agent (ant) and consequently its behaviour is driven by pheromone strategy, i.e. it tends to choose the routefor which the pheromone level is higher. Results show that our ACS implementation provides good quality solutionswithin an acceptable time. Furthermore, obtained solutions are quite competitive when compared to other stochastictechniques previously studied in literature.
Keywords: Vehicle routing problem with simultaneous delivery and pickup, ant colony system, reverse logistic.
CITE THIS PAPER AS:
Franklin JOHNSON, Jorge VEGA, Guillermo CABRERA, Enrique CABRERA, Ant Colony System for a Problem in Reverse Logistic, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (2), pp. 133-140, 2015.
During the last few decades an increasing number of environmental issues have led to changes in the normative that regulates the logistic industry. In particular, new requirements from customers such as recycling and proper items disposal cause that logistic industry should not only look at the delivery process but also to the pick-up one. Because of that, well-known Vehicle Routing Problem (VRP) is not an adequate model to the integrated problem mentioned before. Therefore, several new models have been introduced in order to address this new scenario. In this article we consider one of those models namely VRP with simultaneous delivery and pick-up (VRPSDP). VRPSDP problem has been firstly introduced and modelled in . In  authors studied the VRPSDP based on a real case from book distribution industry. They tackled the book logistic activity from one central library to a set of local libraries and vice-versa. They considered a fixed number of vehicles and a limited vehicle capacity. Different mathematical models for the VRPSDP have been proposed in ,  and . Particularly, authors in  modelled the VRPSDP as part of the reverse logistics process. In this paper we attempt to find high quality solutions to this optimisation problem using the well-known Ant Colony Systems (ACS) heuristic.
Ant Colony Systems has demonstrated to be very effective for routing problems . In general it is able to find near-optimal routes for many problems such as VRP [14, 15, 20] and travelling salesman problem [10, 12, 16], among others. One advantage of ACS over other heuristics is its rapid convergence, which means high quality solutions within an acceptable time. To the best of our knowledge, ACS algorithm has only been used to solve the VRPSDP problem in [15, 21]. Although similar strategies are considered, our algorithm implements quite different steps and rules which make our approach substantially different from those previously presented approaches. This article is organised as follows: Section 2 presents a literature review and introduces the mathematical model for the VRPSDP that is considered in this study. Section 3 reviews ACS algorithms and describes in detail the proposed ACS algorithm for the VRPSPD. Section 4 presents the benchmark used in this study. Obtained results are analysed at the end of this section. Finally, some conclusions are outlined in Section 5.
- MIN, H., The Multiple Vehicle Routing Problems with Simultaneous Delivery and Pick-up Points. Transportation Research Part: A, vol. 23, 1989, pp. 377-386.
- DETHLOFF, J., Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up. OR Spektrum, vol. 23, 2001, pp. 79-96.
- NAGY, G., S. SALHI, Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries. European Journal of Operational Research, vol. 162(1), 2005, pp. 126-141.
- MONTANÉ, T., R. GALVÃO, A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service. Computers and Operations Research, vol. 33(3), 2006, pp. 595-619.
- AI, J., KACHITVICHYANUKUL, V., A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, vol. 36, 2009, pp. 1693-1702.
- TANG, F., R. GALVÃO, Vehicle Routing Problems with Simultaneous Pick-up and Delivery Service. Journal of the Operational Research Society of India (OPSEARCH), vol. 39, 2002, pp. 19-33.
- ZACHARIADIS, E., C. TARANTILIS, C. KIRANOUDIS, A Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service. Expert Systems with Applications, vol. 36, 2009, pp. 1070-1081.
- BULLHEIMER, B., R. HARTL, C. STRAUSS, An Improved Ant System Algorithm for the Vehicle Routing Problem. Annals of Operations Research, vol. 89, 1999, pp. 319-328.
- DORIGO, M., T. STÜTZLE, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Handbook of Metaheuristics, International Series in Operations Research and Management Science, vol. 57, 2003, pp. 250-285.
- DORIGO, M., L. GAMBARDELLA, Ant Colonies for the Travelling Salesman Problem. Biosystems vol. 43, 1997, pp. 273-81.
- MANIEZZO, V., L. GAMBARDELLA, F. De LUIGI, Ant Colony Optimization, New Optimization Techniques in Engineering, by Onwubolu and Babu (Eds), Springer-Verlag Berlin Heidelberg, 2004, pp. 101-117.
- DORIGO, M., L. GAMBARDELLA, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation vol. 1, 1996, pp. 53-66.
- BIANCHESSI, N., G. RIGHINI, Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery. Computers & Operations Research, vol. 34(2), 2007, pp. 578-594.
- DING, Q., X. HU, L. SUN, Y. WANG, An Improved Ant Colony Optimization and Its Application to Vehicle Routing Problem with Time Windows. Neurocomputing, vol. 98(3), 2012, pp. 101-107.
- GAJPAL, Y., P. ABAD, An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup. Computers & Operations Research, vol. 36, 2009, pp. 3215-3223.
- JUN-MAN, K., Z. YI, Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem. Energy Procedia, vol. 17, 2012, pp. 319-325.
- RIECK, J., J. ZIMMERMANN, Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. BuR – Business Research, vol. 6(1), 2013, pp. 77-92
- ZHU, N., C. SHAO, Vehicle Routing Problem with Simultaneous Delivery and Pick-up Based on the Improved Genetic Algorithm. Fourth International Conference on Genetic and Evolutionary Computing, 2010, pp. 312-316
- CAO, E., M. LAI, An Improved Differential Evolution Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service. Third International Conference on Natural Computation, 2007, pp. 436-440
- BADR, A., Solving Dynamic Vehicle Routing: An Alternative Metaheuristic Approach, Studies in Informatics and Control, vol. 18 (2), 2009, pp. 159-164.
- ÇATAY, B., A New Saving based Ant Algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Expert Systems with Applications, vol. 37 (10), 2010, pp. 6809-6817.