Abstract
The main contribution of the paper is to propose and validate a new agent-based method of solving instances of the Capacited Vehicle Routing Problem (CVRP). The approach adopts a guided local search metaheuristic and combines it with an asynchronous team (A-Team) concept. A-Team assumes that a collection of software agents, each representing a particular problem solving method, cooperate to solve a problem by dynamically evolving a population of solutions. In suggested implementation each software agent carries out a guided local search. The paper contains the CVRP formulation, an overview of the dedicated multi-agent framework and a description of the proposed implementation for solving CVRP. The approach is validated experimentally and results of computational experiment are included in the final part of the paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backer, B.D., Furnon, V., Prosser, P., Kilby, P., Shaw, P.: Solving vehicle routing problems using constraint programming and metaheuristics. Journal of Heuristics 6(4), 501–523 (2000)
Barbucha, D., Jędrzejowicz, P.: Agent-Based Approach to the Dynamic Vehicle Routing Problem. In: Demazeau, Y., Pavon, J., Corchado, J.M., Bajo, J. (eds.) 7th Int. Conf. on Practical Applications of Agents and Multi-Agent Systems, Advances in Intelligent and Soft Computing, vol. 55, pp. 169–178. Springer, Berlin (2009)
Barbucha, D.: Cooperative Solution to the Vehicle Routing Problem. In: Jędrzejowicz, P., Nguyen, N.T., Howlet, R.J., Jain, L.C. (eds.) KES-AMSTA 2010. LNCS, vol. 6071, pp. 180–189. Springer, Heidelberg (2010)
Berger, J., Barkaoui, M.: A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society 54, 1254–1262 (2003)
Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.): Combinatorial optimization. John Wiley, Chichester (1979)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12, 568–581 (1964)
Fisher, M.L., Jaikumar, R.: A generalized assignment heuristic for vehicle routing. Networks 11, 109–124 (1981)
Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuristic for the vehicle routing problem. Management Science 40, 1276–1290 (1994)
Gillett, B.E., Miller, L.R.: A heuristic algorithm for the vehicle dispatch problem. Operations Research 22, 240–349 (1974)
Golden, B.L., Raghavan, S., Wasil, E.A. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research Computer Science Interfaces Series, vol. 43. Springer, Heidelberg (2008)
Jennings, N.R., Sycara, K., Wooldridge, M.: A Roadmap of Agent Research and Development. Autonomous Agents and Multi-Agent Systems 1, 7–38 (1998)
Kilby, P., Prosser, P., Shaw, P.: Guided local search for the vehicle routing problem. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 473–486. Kluwer Academic Publishers, Dordrecht (1999)
Kinderwater, G.A.P., Savelsbergh, M.W.P.: Vehicle routing: handling edge exchanges. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 337–360. Wiley, Chichester (1997)
Laporte, G., Gendreau, M., Potvin, J., Semet, F.: Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research 7, 285–300 (2000)
Mester, D., Bräysy, O.: Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers and Operations Research 34, 2964–2975 (2007)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Computers and Operations Research 31, 1985–2002 (2004)
Reimann, M., Doerner, K., Hartl, R.F.: D-ants: savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research 31, 563–591 (2004)
Rochat, Y., Taillard, E.D.: Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics 1(1), 147–167 (1995)
Taillard, E.D.: Parallel iterative search methods for vehicle routing problems. Networks 23, 661–673 (1993)
Talukdar, S., Baeretzen, L., Gove, A., de Souza, P.: Asynchronous teams: Cooperation schemes for autonomous agents. Journal of Heuristics 4, 295–321 (1998)
Thangiah, S.R., Shmygelska, O., Mennell, W.: An agent architecture for vehicle routing problem. In: Proc. of the ACM Symposium on Applied Computing (SAC 2001), Las Vegas, pp. 517-521 (2001)
Thompson, P.M., Psaraftis, H.N.: Cyclic transfer algorithms for the multivehicle routing and scheduling problems. Operations Research 41, 935–946 (1993)
Toth, P., Vigo, D.: The Granular Tabu Search and Its Application to the Vehicle-Routing Problem. INFORMS Journal on Computing 15(4), 333–346 (2003)
Van Breedam, A.: An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and time-related constraints. Ph.D. dissertation, University of Antwerp (1994)
Voudouris, C., Tsang, E.: Partial Constraint Satisfaction Problems and Guided Local Search. In: Proc. of 2nd Int. Conf. on Practical Application of Constraint Technology (PACT 1996), London, pp. 337–356 (1996)
Voudouris, C., Tsang, E.: Guided local search and its application to the traveling salesman problem. European Journal of Operational Research 113, 469–499 (1999)
Xu, J., Kelly, J.P.: A network flow-based tabu search heuristic for the vehicle routing problem. Transportation Science 30, 379–393 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barbucha, D. (2011). An Agent-Based Guided Local Search for the Capacited Vehicle Routing Problem. In: O’Shea, J., Nguyen, N.T., Crockett, K., Howlett, R.J., Jain, L.C. (eds) Agent and Multi-Agent Systems: Technologies and Applications. KES-AMSTA 2011. Lecture Notes in Computer Science(), vol 6682. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22000-5_49
Download citation
DOI: https://doi.org/10.1007/978-3-642-22000-5_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21999-3
Online ISBN: 978-3-642-22000-5
eBook Packages: Computer ScienceComputer Science (R0)