MAX-MIN ANT SYSTEM FOR LOCATION-ROUTING PROBLEMS
Keywords:
Location-Routing Problems, metaheuristic, max-min ant system, local searchAbstract
This work introduces a modified meta-heuristic algorithm for solving Location- Routing Problems(LRP). It presents the most relevant steps towards the implementation of LRP, involving servicing asset of customers from a set of specific capacitated depots by using a set of identical vehicles. The objective of LRP is to minimize the total location and distribution costs. Since LRP is nondeterministic polynomial-time (NP) hard combinatorial problem, the heuristic is an appropriate approach to solve this problem. In this study, a heuristic based on the Max-Min Ant System(MMAS) is proposed and a 2–opt/ Move-Swap algorithm is applied. This approach aims to integrate2 levels of decision making (location-routing) in a computationally efficient manner. Simulations are performed using problem instances available from literature. The results show that the modified MMAS performs efficiently in solving LRP.
References
Bullnheimer, B., Hartl, R.F., and Strauss, C.(1999). An improved ant system for the vehicle routing problem. Ann. Oper. Res.,89:319-328.
Chao, I.M., Golden, B.L., and Wasil, E. (1993).A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. Am. J. Math. Sci.,13 (3-4):371-406.
Chien, W.T. (1993). Heuristic procedures for the practical sized uncapacitated locationcapacitatedrouting problems. Decision Sci., 24:995-1021.
Clarke, G. and Wright, J. (1964), Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res.,12:568-581.
Dang, D.L. (2003). An ant colony algorithm for solving the multi-depot vehicle routing problem. [Msc thesis]. School of Advanced Technologies, Asian Institute of Technology.Pathum Thani, Thailand.
Dorigo, M. and Gambardella L.M. (1997).Ant colonies for the traveling salesman problem. Bio-Systems. 43:73-81
Gillet, B. and Johnson, J. (1976). Multiterminal vehicle dispatch algorithm. Omega,4:711-718.
Ha, D.S. (1998). A hybrid genetic approach for the multi-depot vehicle routing problems, [Msc thesis]. School of Advanced Technologies, Asian Institute of Technology.Pathum Thani, Thailand.
Hansen, P.H., Hegedahl, B., Hjortkjr, S., and Obel, B. (1994). A heuristic solution to the warehouse location-routing problem.Eur. Oper. Res., 76(1):111-127.
Laporte, G. and Norbert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. Eur. J.Oper. Res., 6:224-226.
Laporte, G., Norbert, Y., and Pelletier, P. (1983).Hamiltonian location problems. Eur.Oper. Res., 12:80-87.
Laporte, G., Norbert, Y., and Arpin, D. (1986).An exact algorithm for solving a capacitated location routing problem. Ann. Oper.Res., 6:293-310.
Laporte, G., Norbert, Y., and Taillefer, S.(1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transport. Sci., 22(3):161-172.
Madsen, O.B.G. (1983). Methods for solving combined two level location-routing problems of realistic dimensions. Eur.Oper. Res., 12:295-301.
Nagy, G. and Salhi, S. (1996). Nested heuristic methods for the location-routing problem.J. Oper. Res. Soci., 47:1166 1174.
Pathumnakul, S. (1996). Solving multi depotvehicle routing problem for Iowa recycled paper by Tabu Search heuristic,[Msc thesis]. School of Science, Iowa State University, Ames, IA, U.S.A.
Perl, J. and Daskin, M.S. (1985). A warehouse location-routing problem. Transport.Res., 19B:381-396.
Raft, O.M. (1982). A modular algorithm foran extended vehicle scheduling problem.Eur. J. Oper. Res., 11:67-76.
Renaud, J., Laporte, F., and Boctor, F. (1996).A tabu search for the multi-depot vehicle routing problem. Comput. Oper. Res.,23:229-235.
Sodsoon, S. and Sindhu Chao, S. (2007). AMax Min Ant System for Multi-Depot Routing Problem. Proceedings of the 2thInternational Conference on Operations and Supply Chain Management (OSCM-2007); May 18–20, 2007; Bangkok, Thailand, p.1165–1174.
Stützle, T. and Hoos, H.H. (2000) MAX-MINAnt System, Future Gener. Comp. Sys.,16:889–914.
Tuzun, D. and Burke, L. (1999). A two-phasetabu search approach to the location routing problem, Eur. J. Oper. Res.,116:87-99.
Wu, T., Low, C., and Bai, J. (2002). Heuristic solutions to multi-depot location- routing problems. Comput. Oper. Res., 29(10):1393-1415
Wang, X., Sun, X., and Fang, Y. (2005). A two-phase hybrid heuristic search approach to the location-routing problem,IEEE International Conference on Service Operation and Logistics, and Informatics; August 10-12, 2005; Beijing, China, (4):3338-3343.
