The Bi-Objective k-Dissimilar Vehicle Routing Problem

详细信息    查看全文

• 关键词：Bi ; objective ; k ; dissimilar vehicle routing problem ; Pareto set approximation
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9855
• 期：1
• 页码：306-320
• 全文大小：431 KB
• 参考文献：1.Akgün, V., Erkut, E., Batta, R.: On finding dissimilar paths. Eur. J. Oper. Res. 121(2), 232–246 (2000)CrossRef MATH
  2.Bock, F.: An algorithm for solving ‘Traveling Salesman’ and related network optimization problems. Technical report, 14th National Meeting of the Operations Research Society of America (ORSA), St Louis (1958)
  3.Christofides, N.: Combinatorial optimization. Wiley, Chichester and New York (1979)MATH
  4.Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)CrossRef
  5.Croes, G.A.: A method for solving traveling salesman problems. Oper. Res. 6, 791–812 (1958)CrossRef MathSciNet
  6.Dell’Olmo, P., Gentili, M., Scozzari, A.: On finding dissimilar Pareto-optimal paths. Eur. J. Oper. Res. 162(1), 70–82 (2005)CrossRef MATH
  7.Geiger, M.J.: Fast approximation heuristics for multi-objective vehicle routing problems. In: Chio, C., et al. (eds.) EvoApplications 2010, Part II. LNCS, vol. 6025, pp. 441–450. Springer, Heidelberg (2010)CrossRef
  8.Glover, F.: Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl. Math. 65(1–3), 223–253 (1996)CrossRef MATH MathSciNet
  9.Johnson, P., Joy, D., Clarke, D.: HIGHWAY 3.01, an enhancement routing model: program, description, methodology and revised user’s manual. Technical report, Oak Ridge National Laboratories, Washington, D.C. (1992)
  10.Kuby, M., Zhongyi, X., Xiaodong, X.: A minimax method for finding the k best “differentiated” paths. Geogr. Anal. 29(4), 298–313 (1997)CrossRef
  11.Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(3), 345–358 (1992)CrossRef MATH
  12.Lombard, K., Church, R.L.: The gateway shortest path problem: generating alternative routes for a corridor location problem. Geogr. Syst. 1, 25–45 (1993)
  13.Martí, R., González Velarde, J.L., Duarte, A.: Heuristics for the bi-objective path dissimilarity problem. Comput. Oper. Res. 36(11), 2905–2912 (2009)CrossRef MATH
  14.Ngueveu, S.U., Prins, C., Wolfler Calvo, R.: A hybrid tabu search for the m-peripatetic vehicle routing problem. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics. Annals of Information Systems, vol. 10, pp. 253–266. Springer, Boston (2010)CrossRef
  15.Savelsbergh, M.W.P.: The vehicle routing problem with time windows: minimizing route duration. INFORMS J. Comput. 4, 146–154 (1992)CrossRef MATH
  16.Sörensen, K.: Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics. CEJOR 14(2), 193–207 (2006)CrossRef MATH MathSciNet
  17.Suurballe, J.W.: Disjoint paths in a network. Networks 4(2), 125–145 (1974)CrossRef MATH MathSciNet
  18.Talarico, L., Sörensen, K., Springael, J.: The k-dissimilar vehicle routing problem. Eur. J. Oper. Res. 244(1), 129–140 (2015)CrossRef MathSciNet
  19.Yen, J.Y.: Finding the k shortest loopless paths in a network. Manage. Sci. 17(11), 712–716 (1971)CrossRef MATH MathSciNet
  20.Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)CrossRef
  21.Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998)CrossRef
  
• 作者单位：Sandra Zajac (16)
  
  16. Logistics Management Department, Helmut-Schmidt-University, Holstenhofweg 85, 22043, Hamburg, Germany
  
• 丛书名：Computational Logistics
• ISBN：978-3-319-44896-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9855

文摘

This paper deals with the k-dissimilar vehicle routing problem in which a set of k dissimilar alternatives for a Capacitated Vehicle Routing Problem (CVRP) has to be determined for a single instance. The tradeoff between minimizing the longest routing alternative and maximizing the minimum dissimilarity between two routing alternatives is investigated. Since short vehicle routings tend to be similar to each other, a conflict of objectives arises. The developed heuristic approach approximates the Pareto set with respect to this tradeoff using a dissimilarity metric based on a grid. The method is tested on benchmark instances of the CVRP and findings are reported.