Multi-depot vehicle routing problem: a comparative study of alternative formulations

References

• Alinaghian, M., and N. Shokouhi. 2018. “Multi-depot Multi-compartment Vehicle Routing Problem, Solved by Ahybrid Adaptive Large Neighborhood Search.” Omega 76: 85–99. doi: 10.1016/j.omega.2017.05.002
   Web of Science ®Google Scholar
• Atamturk, A., and M. W. P. Savelsbergh. 2005. “Integer-programming Software Systems.” Annals of Operations Research 140: 67–124. doi: 10.1007/s10479-005-3968-2
   Web of Science ®Google Scholar
• Bae, H., and I. Moon. 2016. “Multi-depot Vehicle Routing Problem with Time Windows Considering Delivery and Installation Vehicles.” Applied Mathematical Modelling 40: 6536–6549. doi: 10.1016/j.apm.2016.01.059
   Web of Science ®Google Scholar
• Baldacci, R., N. Christofides, and A. Mingozzi. 2008. “An Exact Algorithm for the Vehicle Routing Problem Based on the set Partitioning Formulation with Additional Cuts.” Mathematical Programming 115: 351–385. doi: 10.1007/s10107-007-0178-5
   Web of Science ®Google Scholar
• Baldacci, R., E. Hadjiconstantinou, and A. Mingozzi. 2004. “An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-commodity Network Flow Formulation.” Operations Research 52: 723–738. doi: 10.1287/opre.1040.0111
   Web of Science ®Google Scholar
• Baldacci, R., and A. Mingozzi. 2009. “A Unified Exact Method for Solving Different Classes of Vehicle Routing Problems.” Mathematical Programming 120: 347–380. doi: 10.1007/s10107-008-0218-9
   Web of Science ®Google Scholar
• Baldacci, R., P. Toth, and D. Vigo. 2007. “Recent Advances in Vehicle Routing Exact Algorithms.” 4or-a Quarterly Journal of Operations Research 5: 269–298. doi: 10.1007/s10288-007-0063-3
   Google Scholar
• Balinski, M. L., and R. E. Quandt. 1964. “On Integer-Program for Delivery Problem.” Operations Research 12: 300-&. doi: 10.1287/opre.12.2.300
   Web of Science ®Google Scholar
• Bettinelli, A., A. Ceselli, and G. Righini. 2011. “A Branch-and-cut-and-price Algorithm for the Multi-depot Heterogeneous Vehicle Routing Problem with Time Windows.” Transportation Research Part C-Emerging Technologies 19: 723–740. doi: 10.1016/j.trc.2010.07.008
   Web of Science ®Google Scholar
• Bezerra, S. N., S. R. De Souza, and M. J. F. Souza. 2018. “A GVNS Algorithm for Solving the Multi-depot Vehicle Routing Problem.” Electronic Notes in Discrete Mathematics 66: 167–174. doi: 10.1016/j.endm.2018.03.022
   Google Scholar
• Braekers, K., K. Ramaekers, and I. V. Nieuwenh. 2016. “The Vehicle Routing Problem: State of the Art Classification and Review.” Computers & Industrial Engineering 99: 300–313. doi: 10.1016/j.cie.2015.12.007
   Web of Science ®Google Scholar
• Chao, I., B. L. Golden, and E. Wasil. 1993. “A new Heuristic for the Multi-depot Vehicle Routing Problem Taht Improves upon Best-known Solutions.” American Journal of Mathematical and Management Sciences 13: 371–406. doi: 10.1080/01966324.1993.10737363
   Google Scholar
• Chávez, J. J. S., J. W. Escobar, and M. G. Echeverri. 2016. “A Multi-objective Pareto and Colony Algorithm for the Multi-depot Vehicle Routing Problem with Backhauls.” International Journal of Industrial Engineering Computations 7: 35–48. doi: 10.5267/j.ijiec.2015.8.003
   Google Scholar
• Contardo, C., and R. Martinelli. 2014. “A new Exact Algorithm for the Multi-depot Vehicle Routing Problem Under Capacity and Route Length Constraints.” Discrete Optimization 12: 129–146. doi: 10.1016/j.disopt.2014.03.001
   Web of Science ®Google Scholar
• Cordeau, J. F., M. Gendreau, and G. Laporte. 1997. “A Tabu Search Heuristic for Periodic and Multi-depot Vehicle Routing Problems.” Networks 30: 105–119. doi: 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
   Web of Science ®Google Scholar
• Crevier, B., J. F. Cordeau, and G. Laporte. 2007. “The Multi-depot Vehicle Routing Problem with Inter-depot Routes.” European Journal of Operational Research 176: 756–773. doi: 10.1016/j.ejor.2005.08.015
   Web of Science ®Google Scholar
• Dantzig, G., R. Fulkerson, and S. Johnson. 1954. “Solution of a Large-scale Traveling-Salesman Problem.” Journal of the Operations Research Society of America 2: 393–410. doi: 10.1287/opre.2.4.393
   Web of Science ®Google Scholar
• Dondo, R. G. D. R. G., and J. Cerda. 2009. “A Hybrid Local Improvement Algorithm for Large-scale Multi-depot Vehicle Routing Problems with Time Windows.” Computers & Chemical Engineering 33: 513–530. doi: 10.1016/j.compchemeng.2008.10.003
   Web of Science ®Google Scholar
• Du, J., X. Li, L. Yu, R. Dan, and J. Zou. 2017. “Multi-depot Vehicle Routing Problem for Hazardous Materials Transportation: A Fuzzy Bilevel Programming.” Information Sciences 399: 201–218. doi: 10.1016/j.ins.2017.02.011
   Web of Science ®Google Scholar
• Dueck, G. 1993. “New Optimization Heuristics – the Great Deluge Algorithm and the Record-to-record Travel.” Journal of Computational Physics 104: 86–92. doi: 10.1006/jcph.1993.1010
   Web of Science ®Google Scholar
• Escobar, J. W., R. Linfati, P. Toth, and M. G. Baldoquin. 2014. “A Hybrid Granular Tabu Search Algorithm for the Multi-depot Vehicle Routing Problem.” Journal of Heuristics 20: 483–509. doi: 10.1007/s10732-014-9247-0
   Web of Science ®Google Scholar
• Finke, G., A. Claus, and E. Gunn. 1984. “A two-Commodity Network flow Approach to the Traveling Salesman Problem.” Congressus Numerantium 41: 167–178.
   Google Scholar
• Fukasawa, R., H. Longo, J. Lysgaard, M. P. De Aragao, M. Reis, E. Uchoa, and R. F. Werneck. 2006. “Robust Branch-and-cut-and-price for the Capacitated Vehicle Routing Problem.” Mathematical Programming 106: 491–511. doi: 10.1007/s10107-005-0644-x
   Web of Science ®Google Scholar
• Ganesh, K., and T. T. Narendran. 2008. “TASTE: A Two-phase Heuristic to Solve a Routing Problem with Simultaneous Delivery and Pick-up.” International Journal of Advanced Manufacturing Technology 37: 1221–1231. doi: 10.1007/s00170-007-1056-2
   Web of Science ®Google Scholar
• Gillet, B., and J. Johnson. 1976. “Multi-terminal Vehicle Dispatching Algorithm.” Omega 4: 711–718. doi: 10.1016/0305-0483(76)90097-9
   Web of Science ®Google Scholar
• Golden, B. L., T. L. Magnanti, and H. Q. Nguyen. 1977. “Implementing Vehicle Routing Algorithms.” Networks 7: 113–148. doi: 10.1002/net.3230070203
   Web of Science ®Google Scholar
• Gulczynski, D., B. Golden, and E. Wasil. 2011. “The Multi-depot Split Delivery Vehicle Routing Problem: An Integer Programming-Based Heuristic, New Test Problems, and Computational Results.” Computers & Industrial Engineering 61: 794–804. doi: 10.1016/j.cie.2011.05.012
   Web of Science ®Google Scholar
• Ho, W., G. T. S. Ho, P. Ji, and H. C. W. Lau. 2008. “A Hybrid Genetic Algorithm for the Multi-depot Vehicle Routing Problem.” Engineering Applications of Artificial Intelligence 21: 548–557. doi: 10.1016/j.engappai.2007.06.001
   Web of Science ®Google Scholar
• Kara, I., G. Laporte, and T. Bektas. 2004. “A Note on the Lifted Miller-Tucker-Zemlin Subtour Elimination Constraints for the Capacitated Vehicle Routing Problem.” European Journal of Operational Research 158: 793–795. doi: 10.1016/S0377-2217(03)00377-1
   Web of Science ®Google Scholar
• Kohl, N., and O. B. G. Madsen. 1997. “An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation.” Operations Research 45: 395–406. doi: 10.1287/opre.45.3.395
   Web of Science ®Google Scholar
• Laporte, G., Y. Nobert, and D. Arpin. 1984. “Optimal Solutions to Capacitated Multi-depot Vehicle Routing Problems.” Congressus Numerantium 44: 283–292.
   Google Scholar
• Laporte, G., Y. Nobert, and M. Desrochers. 1985. “Optimal Routing Under Capacity and Distance Restrictions.” Operations Research 33: 1050–1073. doi: 10.1287/opre.33.5.1050
   Web of Science ®Google Scholar
• Laporte, G., Y. Nobert, and S. Taillefer. 1988. “Solving a Family of Multi-depot Vehicle-routing and Location-routing Problems.” Transportation Science 22: 161–172. doi: 10.1287/trsc.22.3.161
   Web of Science ®Google Scholar
• Li, J., Y. Li, and P. M. Pardalos. 2016. “Multi-depot Vehicle Routing Problem with Time Windows Under Shared Depot Resources.” Journal of Combinatorial Optimization 31: 515–532. doi: 10.1007/s10878-014-9767-4
   Web of Science ®Google Scholar
• Lim, A., and F. Wang. 2005. “Multi-depot Vehicle Routing Problem: A one-Stage Approach.” Ieee Transactions on Automation Science and Engineering 2: 397–402. doi: 10.1109/TASE.2005.853472
   Web of Science ®Google Scholar
• Mancini, S. 2016. A Real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search Based Matheuristic.” Transportation Research Part C: Emerging Technologies 70: 100–112. doi: 10.1016/j.trc.2015.06.016
   Web of Science ®Google Scholar
• Miller, C. E., A. W. Tucker, and R. A. Zemlin. 1960. “Integer Programming Formulation of Traveling Salesman Problems.” Journal of the Acm 7: 326–329. doi: 10.1145/321043.321046
   Web of Science ®Google Scholar
• Montoya-Torres, J. R., J. L. Franco, S. N. Isaza, H. F. Jimenez, and N. Herazo-Padilla. 2015. “A Literature Review on the Vehicle Routing Problem with Multiple Depots.” Computers & Industrial Engineering 79: 115–129. doi: 10.1016/j.cie.2014.10.029
   Web of Science ®Google Scholar
• Muter, I., J. F. Cordeau, and G. Laporte. 2014. “A Branch-and-price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes.” Transportation Science 48: 425–441. doi: 10.1287/trsc.2013.0489
   Web of Science ®Google Scholar
• Pataki, G. 2003. “Teaching Integer Programming Formulations Using the Traveling Salesman Problem.” Siam Review 45: 116–123. doi: 10.1137/S00361445023685
   Web of Science ®Google Scholar
• Renaud, J., G. Laporte, and F. F. Boctor. 1996. “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem.” Computers & Operations Research 23: 229–235. doi: 10.1016/0305-0548(95)O0026-P
   Web of Science ®Google Scholar
• Salhi, S., A. Imran, and N. A. Wassan. 2014. “The Multi-depot Vehicle Routing Problem with Heterogeneous Vehicle Fleet: Formulation and a Variable Neighborhood Search Implementation.” Computers & Operations Research 52: 315–325. doi: 10.1016/j.cor.2013.05.011
   Web of Science ®Google Scholar
• Salhi, S., and M. Sari. 1997. “A Multi-level Composite Heuristic for the Multi-depot Vehicle Fleet mix Problem.” European Journal of Operational Research 103: 95–112. doi: 10.1016/S0377-2217(96)00253-6
   Web of Science ®Google Scholar
• Sherali, H. D., and P. J. Driscoll. 2002. “On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems.” Operations Research 50: 656–669. doi: 10.1287/opre.50.4.656.2865
   Web of Science ®Google Scholar
• Tillman, F. A., and T. M. Cain. 1972. “Upperbound Algorithem for Single and Multiple Terminal Delivery Problem.” Management Science Series a-Theory 18: 664–682.
   Google Scholar
• Vidal, T., T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei. 2012. “A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems.” Operations Research 60: 611–624. doi: 10.1287/opre.1120.1048
   Web of Science ®Google Scholar
• Yu, B., N. Ma, W. Cai, T. Li, X. Yuan, and B. Yao. 2013. “Improved Ant Colony Optimisation for the Dynamic Multi-depot Vehicle Routing Problem.” International Journal of Logistics Research and Applications 16: 144–157. doi: 10.1080/13675567.2013.810712
   Web of Science ®Google Scholar
• Yucenur, G. N., and N. C. Demirel. 2011. “A New Geometric Shape-based Genetic Clustering Algorithm for the Multi-depot Vehicle Routing Problem.” Expert Systems with Applications 38: 11859–11865. doi: 10.1016/j.eswa.2011.03.077
   Web of Science ®Google Scholar
• Zhang, Y., M. Qi, L. Miao, and G. Wu. 2015. “A Generalized Multi-depot Vehicle Routing Problem with Replenishment Based on LocalSolver.” International Journal of Industrial Engineering Computations 6: 81–98. doi: 10.5267/j.ijiec.2014.8.005
   Google Scholar