An Approximation Algorithm for k-Depot Split Delivery Vehicle Routing Problem

References

• Archetti C, Speranza MG (2008) The Split Delivery Vehicle Routing Problem: A Survey. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York), 103–122.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2014) Branch-and-cut algorithms for the split delivery vehicle routing problem. Eur. J. Oper. Res. 238(3):685–698.Crossref, Google Scholar
• Archetti C, Savelsbergh MW, Speranza MG (2006a) Worst-case analysis for split delivery vehicle routing problems. Transportation Sci. 40(2):226–234.Link, Google Scholar
• Archetti C, Speranza MG, Hertz A (2006b) A tabu search algorithm for the split delivery vehicle routing problem. Transportation Sci. 40(1):64–73.Link, Google Scholar
• Archetti C, Speranza MG, Savelsbergh MW (2008) An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Sci. 42(1):22–31.Link, Google Scholar
• Belenguer JM, Martinez M, Mota E (2000) A lower bound for the split delivery vehicle routing problem. Oper. Res. 48(5):801–810.Link, Google Scholar
• Bianchessi N, Irnich S (2019) Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Sci. 53(2):442–462.Link, Google Scholar
• Bianchessi N, Drexl M, Irnich S (2019) The split delivery vehicle routing problem with time windows and customer inconvenience constraints. Transportation Sci. 53(4):1067–1084.Link, Google Scholar
• Bortfeldt A, Yi J (2020) The split delivery vehicle routing problem with three-dimensional loading constraints. Eur. J. Oper. Res. 282(2):545–558.Crossref, Google Scholar
• Chen S, Golden B, Wasil E (2007) The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks 49(4):318–329.Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Davendra D (2010) Traveling Salesman Problem: Theory and Applications (InTech, Rijeka, Croatia).Crossref, Google Scholar
• Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.Link, Google Scholar
• Dethloff J (2002) Relation between vehicle routing problems: An insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls. J. Oper. Res. Soc. 53(1):115–118.Crossref, Google Scholar
• Gary MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-completeness (WH Freeman and Company, New York).Google Scholar
• Gørtz IL, Nagarajan V (2016) Locating depots for capacitated vehicle routing. Networks 68(2):94–103.Crossref, Google Scholar
• Gulczynski D, Golden B, Wasil E (2011) The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Comput. Indust. Engrg. 61(3):794–804.Crossref, Google Scholar
• Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4):422–437.Crossref, Google Scholar
• Harks T, König FG, Matuschke J (2013) Approximation algorithms for capacitated location routing. Transportation Sci. 47(1):3–22.Link, Google Scholar
• Hu Y (2009) Approximation algorithms for the capacitated vehicle routing problem. PhD thesis, Simon Fraser University, Canada.Google Scholar
• Korte B, Vygen J (2018) Combinatorial Optimization: Theory and Algorithms, 6th ed., chapter 11. Weighted Matching (Springer, New York), 277–304.Crossref, Google Scholar
• Lai X, Xu L, Xu Z, Du Y (2023) An approximation algorithm for k-depot split delivery vehicle routing problem. http://dx.doi.org/10.1287/ijoc.2021.0193.cd, https://github.com/INFORMSJoC/2021.0193.Google Scholar
• Li CL, Simchi-Levi D (1990) Worst-case analysis of heuristics for multidepot capacitated vehicle routing problem. ORSA J. Comput. 2(1):64–73.Link, Google Scholar
• Lim A, Wang F (2005) Multi-depot vehicle routing problem: A one-stage approach. IEEE Trans. Autom. Sci. Engrg. 2(4):397–402.Crossref, Google Scholar
• Luo Z, Qin H, Zhu W, Lim A (2017) Branch-and-price-and-cut for the split-collection vehicle routing problem with time windows and linear weight-related cost. Transportation Sci. 51(2):668–687.Link, Google Scholar
• Mehrjerdi YZ, Nadizadeh A (2013) Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. Eur. J. Oper. Res. 229(1):75–84.Crossref, Google Scholar
• Mole R, Jameson S (1976) A sequential route-building algorithm employing a generalised savings criterion. J. Oper. Res. Soc. 27(2):503–511.Crossref, Google Scholar
• Montoya-Torres JR, Franco JL, Isaza SN, Jiménez HF, Herazo-Padilla N (2015) A literature review on the vehicle routing problem with multiple depots. Comput. Indust. Engrg. 79:115–129.Crossref, Google Scholar
• Muyldermans L, Beullens P, Cattrysse D, Van Oudheusden D (2005) Exploring variants of 2-opt and 3-opt for the general routing problem. Oper. Res. 53(6):982–995.Link, Google Scholar
• Papadimitriou CH, Steiglitz K (1998) Combinatorial Optimization: Algorithms and Complexity (Courier Corporation, Mineola, New York).Google Scholar
• Potvin JY (2009) State-of-the art review-evolutionary algorithms for vehicle routing. INFORMS J. Comput. 21(4):518–548.Link, Google Scholar
• Potvin JY, Kervahut T, Garcia BL, Rousseau JM (1996) The vehicle routing problem with time windows part i: Tabu search. INFORMS J. Comput. 8(2):158–164.Link, Google Scholar
• Rathinam S (2007) Routing and Monitoring algorithms for UAVs. PhD thesis, University of California, Berkeley.Google Scholar
• Rathinam S, Sengupta R, Darbha S (2007) A resource allocation algorithm for multi-vehicle systems with non holonomic constraints. IEEE Trans. Autom. Sci. Engrg. 4(1):98–104.Crossref, Google Scholar
• Renaud J, Laporte G, Boctor FF (1996) A tabu search heuristic for the multi-depot vehicle routing problem. Comput. Oper. Res. 23(3):229–235.Crossref, Google Scholar
• Salhi S, Nagy G (1999) A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J. Oper. Res. Soc. 50(10):1034–1042.Crossref, Google Scholar
• SCRC SME (2003) Success with hub and spoke distribution. Accessed June 26, 2022, https://scm.ncsu.edu/scm-articles/article/success-with-hub-and-spoke-distribution.Google Scholar
• Xu Z, Rodrigues B (2015) A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS J. Comput. 27(4):636–645.Link, Google Scholar
• Xu Z, Rodrigues B (2017) An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. Eur. J. Oper. Res. 257(3):735–745.Crossref, Google Scholar
• Xu Z, Xu L, Rodrigues B (2011) An analysis of the extended Christofides heuristic for the k-depot TSP. Oper. Res. Lett. 39:218–223.Crossref, Google Scholar
• Yang X, Liu Z, Li F, Xu Z (2021) Integrated production and transportation scheduling with order-dependent inventory holding costs. Comput. Oper. Res. 136:105477.Crossref, Google Scholar