The shortest tour distance for visiting all points exactly once and returning to the origin is computed by solving the well-known traveling salesman problem (TSP). Owing to the large computational effort needed for optimizing TSP tours, researchers have developed approximations that relate the average length of TSP tours to the number of points, n, visited per tour. The existing approximations are used in transportation system planning and evaluation for estimating the distance for vehicles with large capacities (e.g., delivery trucks) where n is relatively large. However, the average TSP tour lengths would be inaccurately estimated if the approximations were derived for a wide range of n values since the tour lengths increase at a decreasing rate (i.e., with ) as n increases. A comprehensive review is presented here of existing studies approximating TSP tour lengths for low n values, which have become important for some recently favored delivery alternatives (e.g., deliveries by bikes, drones, and robots).
ApplegateD.BixbyR.ChvatalV.CookW.The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, 2006.
2.
AnsariS.BasdereM.LiX.OuyangY.SmilowitzK.Advancements in Continuous Approximation Models for Logistics and Transportation Systems: 1996–2016. Transportation Research Part B: Methodological, Vol. 107, 2018, pp. 229–252. https://doi.org/10.1016/j.trb.2017.09.019
ChangS. K.SchonfeldP.Optimization Models for Comparing Conventional and Subscription Bus Feeder Services. Transportation Science, Vol. 25. No. 4, 1991, pp. 281–298. https://doi.org/10.1287/trsc.25.4.281.
5.
KimM.SchonfeldP.Integration of Conventional and Flexible Bus Services with Timed Transfers. Transportation Research Part B: Methodological, Vol. 68, 2014, pp. 76–97. https://doi.org/10.1016/j.trb.2014.05.017.
6.
ChoiY.SchonfeldP.LeeY.ShinH.Innovative Methods for Delivering Fresh Food to Underserved Populations. Journal of Transportation Engineering, Part A: Systems, Vol. 147, No. 1, 2021, p. 04020140. https://doi.org.10.1061/JTEPBS.0000464.
7.
Holguín-VerasJ.PatilG. R.Observed Trip Chain Behavior of Commercial Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2005. 1906: 74–80.
8.
MahalanobisP.A Sample Survey of the Acreage under Jute in Bengal. The Indian Journal of Statistics, Vol. 4, No. 4, 1940, pp. 511–530. https://www.jstor.org/stable/40383954.
9.
MarksE.A Lower Bound for the Expected Travel Among m Random Points. The Annals of Mathematical Statistics, Vol. 19, No. 3, 1948, pp. 419–422. https://www.jstor.org/stable/2235651.
10.
BeardwoodJ.HaltonJ.HammersleyJ.The Shortest Path through Many Points. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 55, No. 4, 1959, pp. 299–327.
11.
SteinD. M.An Asymptotic Probabilistic Analysis of a Routing Problem. Mathematics of Operations Research, Vol 3. No. 2. 1978, pp. 89–101. https://www.jstor.org/stable/3689335.
12.
OngH. L.HuangH. C.Asymptotic Expected Performance of Some TSP Heuristics: An Empirical Evaluation. European Journal of Operational Research, Vol. 43, 1989, pp. 231–238. https://doi.org/10.1016/0377-2217(89)90217-8.
13.
FiechterC.A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems. Discrete Applied Mathematics, Vol. 51, 1994, pp. 243–267. https://doi.org/10.1016/0166-218X(92)00033-I.
14.
LeeJ.ChoiM. Y.Optimization by Multicanonical Annealing and the Traveling-Salesman Problem. Computer Simulation Studies in Condensed-Matter Physics VII, Vol. 78, 1994, pp. 193–198.
15.
PercusA.MartinO.Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem. Physical Review Letter, Vol. 76, 1996, pp. 1188–1191. https://doi.org/10.1103/PhysRevLett.76.1188.
16.
JohnsonD.McGeochL.RothbergE.Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. Proc., 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, 1996, pp. 341–350.
17.
FranceschettiA.JabaliO.LaporteG.Continuous Approximation Models in Freight Distribution Management. TOP, Vol. 25, 2017, pp. 413–433. https://doi.org/10.1007/s11750-017-0456-1.
FinchS.Mathematical Constants. Cambridge University Press, Cambridge, 2003.
20.
ChristofidesN.EilonS.Expected Distances in Distribution Problems. OR, Vol. 20, No. 4, 1969, pp. 437–443. http://doi.org/10.2307/3008762.
21.
DaganzoC.The Length of Tour in Zones of Different Shapes. Transportation Research Part B: Methodology, Vol. 18B, No. 2, 1984, pp. 135–145. https://doi.org/10.1016/0191-2615(84)90027-4.
22.
BrunettiR.KrauthW.MézardM.ParisiG.Extensive Numerical Simulations of Weighted Matchings: Total Length and Distribution of Links in the Optimal Solution. EPL (Europhysics Letters), Vol. 14, No. 4. 1991, p. 295. https://doi.org/10.1209/0295-5075/14/4/002.
23.
ChienT. W.Operational Estimators for the Length of a Traveling Salesman Tour. Computers & Operations Research, Vol. 19, No. 6, 1992, pp. 469–478. https://doi.org/10.1016/0305-0548(92)90002-M.
24.
KwonO.GoldenB.WasilE.Estimating the Length of the Optimal TSP Tour: An Empirical Study Using Regression and Neural Networks. Computers & Operations Research, Vol. 22, No. 10, 1995, pp. 1039–1046. https://doi.org/10.1016/0305-0548(94)00093-N.
25.
HindleA.WorthingtonD.Models to Estimate Average Route Lengths in Different Geographical Environments. Journal of the Operational Research Society, Vol. 55, 2004, pp. 662–666. https://doi.org/10.1057/palgrave.jors.2601751.
26.
RobustéF.EstradaM.López-PitaA.Formulas for Estimating Average Distance Traveled in Vehicle Routing Problems in Elliptic Zones. Transportation Research Record: Journal of the Transportation Research Board, 2004. 1873: 64–69.
27.
FigliozziM.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. 2089: 1–8.
28.
MeiX.Approximating the Length of Vehicle Routing Problem Solutions Using Complementary Spatial Information. George Mason University, 2005. http://mars.gmu.edu/handle/1920/9623Accessed July 26, 2020.
29.
NicolaD.VetscheraR.DragomirA.Total Distance Approximations for Routing Solutions. Computers and Operations Research, Vol. 102. 2019, pp. 67–74. https://doi.org/10.1016/j.cor.2018.10.008.
30.
KumarS.PanneerselvamR.A Survey on the Vehicle Routing Problem and its Variants. Intelligent Information Management, Vol. 4. No. 3. 2012, pp. 66–74. http://dx.doi.org/10.4236/iim.2012.43010.
CavdarB.SokolJ.A Distribution-Free TSP Tour Length Estimation Model for Random Graphs. European Journal of Operational Research, Vol. 243, No. 2, 2015, pp. 588–598. https://doi.org/10.1016/j.ejor.2014.12.020.
33.
KaufmanA.KingG.KomisarchikM.How to Measure Legislative District Compactness If You Only Know it When You See it. American Journal of Political Science, Vol. 65, No. 3, 2021, pp. 533–550.
34.
ZunicJ.RosinP.A New Convexity Measure for Polygons. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 7, 2004, pp. 923–934.
RoteG., The Degree of Convexity. EuroCG 2013, Braunschweig, Germany, 2013.
37.
MolerC.Numerical Computing with MATLAB. Society for Industrial and Applied Mathematics, 2008.
38.
AdewoleA.OtubamowoK.EgunjobiT.A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem. International Journal of Applied Information Systems, Vol. 4. No. 4, 2012, pp. 6–12.
39.
GuptaD.Solving TSP Using Various Meta-Heuristic Algorithms. International Journal of Recent Contributions from Engineering, Science & IT, Vol 1, No 2, 2013, pp. 22–26.
40.
DamghanijaziE.MazidiA.Meta-Heuristic Approaches for Solving Travelling Salesman Problem. International Journal of Advanced Research in Computer Science, Vol. 8, No. 5, 2017, pp. 18–23.
41.
AbdulkarimH.AlshammariI.Comparison of Algorithms for Solving Traveling Salesman Problem. International Journal of Engineering and Advanced Technology, Vol. 4, No. 6, 2015, pp. 76–79.
42.
GuptaS.RanaA.KansalV.Comparison of Heuristic Techniques: A Case of TSP. Proc., 10th International Conference on Cloud Computing, Data Science & Engineering, Noida, India, 2020. https://doi.org/10.1109/Confluence47617.2020.9058211.
43.
CrisanG.NechitaE.SimianD.On Randomness and Structure in Euclidean TSP Instances: A Study with Heuristic Methods. IEEE Access, Vol. 9. 2021, pp. 5312–5331. https://doi.org/10.1109/ACCESS.2020.3048774.
44.
AntosiewiczM.KolochG.KamińskiB.Choice of Best Possible Metaheuristic Algorithm for the Travelling Salesman Problem with Limited Computational Time: Quality, Uncertainty and Speed. Journal of Theoretical and Applied Computer Science, Vol. 7, No. 1, 2013, pp. 46–55.
45.
GreenS.How Many Subjects Does It Take To Do A Regression Analysis. Multivariate Behavioral Research, Vol. 26, 1991, pp. 499–510. https://doi.org/10.1207/s15327906mbr2603_7.
46.
YangH.LiangX.ZhangZ.LiuY.AbidM.Statistical Modeling of Quartiles, Standard Deviation, and Buffer Time Index of Optimal Tour in Traveling Salesman Problem and Implications for Travel Time Reliability. Transportation Research Record: Journal of the Transportation Research Board, 2020. 2674: 339–347.
