Improving analytic approximations of TSP tour lengths with adjustment factors

References

• Ansari, S., M. Basdere, X. Li, Y. Ouyang, and K. Smilowitz. 2018. “Advancements in Continuous Approximation Models for Logistics and Transportation Systems: 1996–2016.” Transportation Research Part B 107:229–252. https://doi.org/10.1016/j.trb.2017.09.019.
   Google Scholar
• Applegate, D., R. Bixby, V. Chvatal, and W. Cook. 1998. “On the Solution of Traveling Salesman Problems”. Documenta Mathematica. International Congress of Mathematicians, 645–656. http://eudml.org/doc/233207.
   Google Scholar
• Applegate, D., R. Bixby, V. Chvatal, and W. Cook. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press.
   Google Scholar
• Ballou, R., H. Rahardja, and N. Sakai. 2002. “Selected Country Circuity Factors for Road Travel Distance Estimation.” Transportation Research Part A: Policy and Practice 36 (9): 843–848. https://doi.org/10.1016/S0965-8564(01)00044-1.
   Web of Science ®Google Scholar
• Beardwood, J., J. Halton, and J. Hammersley. 1959. “The Shortest Path through Many Points.” Mathematical Proceedings of the Cambridge Philosophical Society 55 (4): 299–327. https://doi.org/10.1017/S0305004100034095.
   Google Scholar
• Burgstaller, B., and F. Pillichshammer. 2009. “The Average Distance Between two Points.” Bulletin of the Australian Mathematical Society 80 (3): 353–359. https://doi.org/10.1017/S0004972709000707.
   Web of Science ®Google Scholar
• Cavdar, B., and J. Sokol. 2015. “A Distribution-free TSP Tour Length Estimation Model for Random Graphs.” European Journal of Operational Research 243 (2): 588–598. https://doi.org/10.1016/j.ejor.2014.12.020.
   Web of Science ®Google Scholar
• Chien, W. 1992. “Operational Estimators for the Length of a Traveling Salesman Tour.” Computers & Operations Research 19 (6): 469–478. https://doi.org/10.1016/0305-0548(92)90002-M.
   Web of Science ®Google Scholar
• Choi, Y. 2021. “Adjustment Factors and Applications for Analytic Approximations of Tour Lengths.” Dissertation, University of Maryland. https://www.proquest.com/openview/c1f3ca0d4a5e5e28c828593cbc7ea9c4/1?pq-origsite=gscholar&cbl=18750&diss=y.
   Google Scholar
• Choi, Y., and P. Schonfeld. 2021a. “A Comparison of Optimized Deliveries by Drones and Trucks.” Transportation Planning and Technology 44 (3): 319–336. https://doi.org/10.1080/03081060.2021.1883230.
   Web of Science ®Google Scholar
• Choi, Y., and P. Schonfeld. 2021b. “Review of Length Approximations for Tours with Few Stops.” Transportation Research Record 2676 (3): 201–213. https://doi.org/10.1177/03611981211049433.
   Web of Science ®Google Scholar
• Christofides, N., and S. Eilon. 1969. “Expected Distances in Distribution Problems.” Operational Research Quarterly 20 (4): 437–443. https://doi.org/10.2307/3008762.
   Google Scholar
• Daganzo, C. 1984. “The Length of Tour in Zones of Different Shapes.” Transportation Research Part B: Methodology 18B (2): 135–145. https://doi.org/10.1016/0191-2615(84)90027-4.
   Google Scholar
• Figliozzi, M. 2008. “Planning Approximations to the Average Length of Vehicle Routing Problems with Varying Customer Demands and Routing Constraints.” Transportation Research Record: Journal of the Transportation Research Board 2008 (1): 1–8. https://doi.org/10.3141/2089-01.
   Google Scholar
• Finch, S. 2003. Mathematical Constants. Cambridge: Cambridge University Press.
   Google Scholar
• Franceschetti, A., O. Jabali, and G. Laporte. 2017. “Continuous Approximation Models in Freight Distribution Management.” TOP 25 (3): 413–433. https://doi.org/10.1007/s11750-017-0456-1.
   Web of Science ®Google Scholar
• Helsgaun, K. 2009. “General k-opt Submoves for the Lin–Kernighan TSP heuristic.” Mathematical Programming Computation 1 (2–3): 119–193. https://doi.org/10.1007/s12532-009-0004-6.
   Google Scholar
• Hindle, A., and D. Worthington. 2004. “Models to Estimate Average Route Lengths in Different Geographical Environments.” Journal of the Operational Research Society 55:662–666. https://doi.org/10.1057/palgrave.jors.2601751.
   Web of Science ®Google Scholar
• Hoos, H., and T. Stuzle. 2014. “On the Empirical Scaling of Run-time for Finding Optimal Solutions to the Travelling Salesman Problem.” European Journal of Operational Research 238 (1): 87–94. https://doi.org/10.1016/j.ejor.2014.03.042.
   Web of Science ®Google Scholar
• Jennings, D., and M. Figliozzi. 2019. “Study of Sidewalk Autonomous Delivery Robots and Their Potential Impacts on Freight Efficiency and Travel.” Transportation Research Record 2673 (6):317–326. https://doi.org/10.1177/0361198119849398.
   Web of Science ®Google Scholar
• Kim, M., J. Levy, and P. Schonfeld. 2019. “Optimal Zone Sizes and Headways for Flexible-route Bus Services.” Transportation Research Part B: Methodological 130: 67–81. https://doi.org/10.1016/j.trb.2019.10.006.
   Web of Science ®Google Scholar
• Kim, E., P. Schonfeld, A. Roche, and C. Raleigh. 2022. “Optimal Service Zones and Frequencies for Flexible-route Freight Deliveries.” Transportation Research Part A: Policy and Practice 159: 182–199. https://doi.org/10.1016/j.tra.2022.03.030.
   Web of Science ®Google Scholar
• Kou, S., B. Golden, and S. Poikonen. 2022. “Optimal TSP Tour Length Estimation Using Standard Deviation as a Predictor.” Computers and Operations Research 148:105993. https://doi.org/10.1016/j.cor.2022.105993.
   Web of Science ®Google Scholar
• Krarup, J., and P. Pruzan. 1980. “The Impact of Distance on Location Problems.” European Journal of Operational Research 4 (4): 256–269. https://doi.org/10.1016/0377-2217(80)90110-1.
   Web of Science ®Google Scholar
• Kumar, S., and R. Panneerselvam. 2012. “A Survey on the Vehicle Routing Problem and its Variants.” Intelligent Information Management 4 (3): 66–74. https://doi.org/10.4236/iim.2012.43010.
   Google Scholar
• Kwon, O., B. Golden, and E. Wasil. 1995. “Estimating the Length of the Optimal TSP tour: An Empirical Study Using Regression and Neural Networks.” Computers & Operations Research 22 (10): 1039–1046. https://doi.org/10.1016/0305-0548(94)00093-N.
   Web of Science ®Google Scholar
• Larson, R., and A. Odoni. 1981. “Urban Operation Research.” Dynamic Ideas.
   Google Scholar
• Lei, H., G. Laporte, Y. Liu, and T. Zhang. 2015. “Dynamic Design of Sales Territories.” Computers & Operations Research 56:84–92. https://doi.org/10.1016/j.cor.2014.11.008.
   Web of Science ®Google Scholar
• Luo, Y., B. Golden, S. Poikonen, and R. Zhang. 2022. “A Fresh Look at the Traveling Salesman Problem with a Center.” Computers & Operations Research 143:105748. https://doi.org/10.1016/j.cor.2022.105748.
   Web of Science ®Google Scholar
• Madani, A., R. Batta, and M. Karwan. 2020. “The Balancing Traveling Salesman Problem: Application to Warehouse Order Picking.” TOP. https://doi.org/10.1007/s11750-020-00557-y.
   Web of Science ®Google Scholar
• Mahalanobis, P. A. 1940. “Sample Survey of the Acreage under Jute in Bengal.” The Indian Journal of Statistics 4 (4): 511–530. https://www.jstor.org/stable/40383954.
   Google Scholar
• Mei, X. 2015. “Approximating the Length of Vehicle Routing Problem Solutions Using Complementary Spatial Information.” Ph.D. Dissertation, George Mason University. http://mars.gmu.edu/handle/1920/9623.
   Google Scholar
• Mei, X., K. Curtin, D. Turner, N. Waters, and M. Rice. 2023. “Approximating the Length of Vehicle Routing Problem Solutions Using Complementary Spatial Information.” Geographical Analysis 55 (1): 125–154. https://doi.org/10.1111/gean.12322.
   Web of Science ®Google Scholar
• Nagata, Y., and S. Kobayashi. 2013. “A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem.” INFORMS Journal on Computing 25 (2): 346–363. https://doi.org/10.1287/ijoc.1120.0506.
   Web of Science ®Google Scholar
• National Academies of Sciences, Engineering, and Medicine. 2010. Freight-demand Modeling to Support Public-sector Decision Making. The National Academies Press. https://doi.org/10.17226/14445.
   Google Scholar
• Nicola, D., R. Vetschera, and A. Dragomir. 2019. “Total Distance Approximations for routing solutions.” Computers and Operations Research 102:67–74. https://doi.org/10.1016/j.cor.2018.10.008.
   Web of Science ®Google Scholar
• Robusté, F., M. Estrada, and A. López-Pita. 2004. “Formulas for Estimating Average Distance Traveled in Vehicle Routing Problems in Elliptic Zones.” Transportation Research Record: Journal of the Transportation Research Board 1873 (1): 64–69. https://doi.org/10.3141/1873-08.
   Google Scholar
• Stein, D. 1977. “Scheduling Dial-a-ride Transportation Systems: An Asymptotic Approach.” Ph.D. Dissertation, Harvard University, Cambridge, MA.
   Google Scholar
• Vinel, A., and D. Silva. 2019. “Probability Distribution of the Length of the Shortest Tour between a Few Random Points: A Simulation Study.” 2018 Winter Simulation Conference (WSC). IEEE, 3156–3167. https://doi.org/10.1109/WSC.2018.8632175.
   Google Scholar