The Traveling Salesman Problem with Stochastic and Correlated Customers

References

• Agresti A (2013) Categorical Data Analysis, 3rd ed. (John Wiley & Sons, New York).Google Scholar
• Applegate D (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Bahadur R (1961) A representation of the joint distribution of responses to n dichotomous items. Stud. Item Anal. Prediction 6:158–168.Google Scholar
• Bakach I, Campbell A, Ehmke J, Urban T (2021) Solving vehicle routing problems with stochastic and correlated travel times and makespan objectives. EURO J. Transportation Logist. 10:100029.Crossref, Google Scholar
• Balaprakash P, Birattari M, Stützle T, Dorigo M (2010) Estimation-based metaheuristics for the probabilistic traveling salesman problem. Comput. Oper. Res. 37(11):1939–1951.Crossref, Google Scholar
• Bent R, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper. Res. 52(6):977–987.Link, Google Scholar
• Beraldi P, Ghiani G, Laporte G, Musmanno R (2005) Efficient neighborhood search for the probabilistic pickup and delivery travelling salesman problem. Networks 45(4):195–198.Crossref, Google Scholar
• Berhan E, Beshah B, Kitaw D, Abraham A (2014) Stochastic vehicle routing problem: A literature survey. J. Inform. Knowledge Management 13(3):1450022.Crossref, Google Scholar
• Bertsimas D (1988) The probabilistic vehicle routing problem. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Bertsimas D (1992) A vehicle routing problem with stochastic demand. Oper. Res. 40(3):574–585.Link, Google Scholar
• Bertsimas D, Howell L (1993) Further results on the probabilistic traveling salesman problem. Eur. J. Oper. Res. 65(1):68–95.Crossref, Google Scholar
• Bianchi L, Gambardella L, Dorigo M (2002) An ant colony optimization approach to the probabilistic traveling salesman problem. Guervós J, Adamidis P, Beyer H, Schwefel H, Fernández-Villacañas J, eds. Proc. 7th Internat. Conf. Parallel Problem Solving Nature PPSN 2002, Lecture Notes in Computer Science, vol. 2439 (Springer-Verlag, Berlin), 883–892.Crossref, Google Scholar
• Birattari M, Balaprakash P, Stützle T, Dorigo M (2008) Estimation-based local search for stochastic combinatorial optimization using delta evaluations: A case study on the probabilistic traveling salesman problem. INFORMS J. Comput. 20(4):644–658.Link, Google Scholar
• Boyer K, Prud’homme A, Chung W (2009) The last mile challenge: Evaluating the effects of customer density and delivery window patterns. J. Bus. Logist. 30(1):185–201.Crossref, Google Scholar
• Brechmann E, Czado C, Aas K (2012) Truncated regular vines in high dimensions with application to financial data. Canad. J. Statist. 40(1):68–85.Crossref, Google Scholar
• Campbell A, Thomas B (2008) Probabilistic traveling salesman problem with deadlines. Transportation Sci. 42(1):1–21.Link, Google Scholar
• Campbell AM, Thomas BW (2009) Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Comput. Oper. Res. 36(4):1231–1248.Crossref, Google Scholar
• Carlsson JG, Behroozi M, Mihic K (2018) Wasserstein distance and the distributionally robust TSP. Oper. Res. 66(6):1603–1624.Link, Google Scholar
• Cherubini U, Luciano E, Vecchiato W (2004) Copula Methods in Finance (John Wiley & Sons, Chichester, UK).Crossref, Google Scholar
• Dantzig G, Ramser J (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• Declerck L, Aerts M, Molenberghs G (1998) Behaviour of the likelihood ratio test statistic under a Bahadur model for exchangeable binary data. J. Stat. Comput. Simulation 61(1–2):15–38.Crossref, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Dell’Amico M, Iori M, Novellani S, Subramanian A (2018) The bike sharing rebalancing problem with stochastic demands. Transportation Res. Part B Methodological 118:362–380.Crossref, Google Scholar
• Denuit M, Lambert P (2005) Constraints on concordance measures in bivariate discrete data. J. Multivariate Anal. 93(1):40–57.Crossref, Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Program. 172(1–2):105–138.Crossref, Google Scholar
• Dorigo M, Gambardella L (1997) Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evolutionary Comput. 1(1):53–66.Crossref, Google Scholar
• European Commission (2021) EU Open Data Portal: Domestic postal traffic, letter mail and parcel services. Accessed July 29, 2022, https://data.europa.eu/euodp/en/data/dataset/6rFQHnqYW7HDFi1hIuDHg.Google Scholar
• Fitzmaurice G, Laird N, Rotnitzky A (1993) Regression models for discrete longitudinal responses. Statist. Sci. 8(3):284–299.Google Scholar
• Frey R, McNeil A (2003) Dependent defaults in models of portfolio credit risk. J. Risk 6:59–92.Crossref, Google Scholar
• Gambardella L, Montemanni R, Weyland D (2012) Coupling ant colony systems with strong local searches. Eur. J. Oper. Res. 220(3):831–843.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (MOS-SIAM, Philadelphia), 213–239.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2016) 50th anniversary invited article—Future research directions in stochastic vehicle routing. Transportation Sci. 50(4):1163–1173.Link, Google Scholar
• Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur. J. Oper. Res. 88(1):3–12.Crossref, Google Scholar
• Genest C, Neálehová J (2007) A primer on copulas for count data. Astin Bull. 37(2):475–515.Crossref, Google Scholar
• Ghosal S, Wiesemann W (2020) The distributionally robust chance-constrained vehicle routing problem. Oper. Res. 68(3):716–732.Link, Google Scholar
• Golden B, Yee Y (1979) A framework for probabilistic vehicle routing. AIIE Trans. 11(2):109–112.Crossref, Google Scholar
• Gordy M (2000) A comparative anatomy of credit risk models. J. Banking Finance 24(1–2):119–149.Crossref, Google Scholar
• Gounaris C, Repoussis P, Tarantilis C, Wiesemann W, Floudas C (2016) An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Sci. 50(4):1239–1260.Link, Google Scholar
• IMRG (2018) IMRG valuing home delivery review 2018. Technical report, Interactive Media in Retail Group, London.Google Scholar
• Jaillet P (1985) Probabilistic traveling salesman problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Jaillet P (1988) A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6):929–936.Link, Google Scholar
• Joe H (1997) Multivariate Models and Multivariate Dependence Concepts (Chapman & Hall/CRC, London).Crossref, Google Scholar
• Kao E (1978) A preference order dynamic program for a stochastic traveling salesman problem. Oper. Res. 26(6):1033–1045.Link, Google Scholar
• Kleywegt A, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Köster F, Ulmer M, Mattfeld D, Hasle G (2018) Anticipating emission-sensitive traffic management strategies for dynamic delivery routing. Transportation Res. Part D Transportation Environ. 62:345–361.Crossref, Google Scholar
• Kruskal J (1983) An overview of sequence comparison: Time warps, string edits, and macromolecules. SIAM Rev. 25(2):201–237.Crossref, Google Scholar
• Kübler J, Reiffer A, Briem L, Vortisch P (2022) Integrating neighbours into an agent-based travel demand model to analyse success rates of parcel deliveries. Procedia Comput. Sci. 201:181–188.Crossref, Google Scholar
• Laporte G, Louveaux F (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Laporte G, Louveaux F, Mercure H (1994) A priori optimization of the probabilistic traveling salesman problem. Oper. Res. 42(3):543–549.Link, Google Scholar
• Laurent J, Gregory J (2005) Basket default swaps, CDOs and factor copulas. J. Risk 7(4):1–20.Crossref, Google Scholar
• Lei H, Laporte G, Guo B (2012) Districting for routing with stochastic customers. EURO J. Transportation Logist. 1(1–2):67–85.Crossref, Google Scholar
• Leipälä T (1978) On the solutions of stochastic traveling salesman problems. Eur. J. Oper. Res. 2(4):291–297.Crossref, Google Scholar
• Letchford A, Nasiri S (2015) The Steiner travelling salesman problem with correlated costs. Eur. J. Oper. Res. 245(1):62–69.Crossref, Google Scholar
• Li W (2017) A simulation-based algorithm for the probabilistic traveling salesman problem. Emmerich M, Deutz A, Schütze O, Legrand P, Tantar E, Tantar A-A, eds. EVOLVE—A Bridge Between Probability, Set Oriented Numerics and Evolutionary Computation VII (Springer, Cham, Switzerland), 157–183.Crossref, Google Scholar
• Liu C, Wang Q, Susilo Y (2019) Assessing the impacts of collection-delivery points to individual’s activity-travel patterns: A greener last mile alternative? Transportation Res. Part E Logist. Transportation Rev. 121:84–99.Crossref, Google Scholar
• Liu YH (2008) A memetic algorithm for the probabilistic traveling salesman problem. Proc. IEEE Congress Evolutionary Comput. CEC 2008 (IEEE, Piscataway, NJ), 146–152.Google Scholar
• Macioszek E (2017) First and last mile delivery—Problems and issues. Sierpinski G, ed. Advanced Solutions of Transport Systems for Growing Mobility: 14th Scientific and Technical Conference “Transport Systems. Theory & Practice 2017” Selected Papers, Advances in Intelligent Systems and Computing, vol. 631 (Springer, Cham, Switzerland), 147–154.Google Scholar
• Mangiaracina R, Perego A, Seghezzi A, Tumino A (2019) Innovative solutions to increase last-mile delivery efficiency in B2C e-commerce: A literature review. Internat. J. Physical Distribution Logist. Management 49(9):901–920.Crossref, Google Scholar
• Marinakis Y, Marinaki M (2010) A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput. Oper. Res. 37(3):432–442.Crossref, Google Scholar
• Marinakis Y, Marinaki M, Migdalas A (2015) Adaptive tunning of all parameters in a multi-swarm particle swarm optimization algorithm: An application to the probabilistic traveling salesman problem. Migdalas A, Karakitsiou A, eds. Optimization, Control, and Applications in the Information Age (Springer, Cham, Switzerland), 187–207.Crossref, Google Scholar
• Molenberghs G, Verbeke G (2005) Models for Discrete Longitudinal Data (Springer-Verlag, New York).Google Scholar
• Nelsen RB (2006) An Introduction to Copulas, 2nd ed. (Springer-Verlag, New York).Google Scholar
• Nešlehová J (2007) On rank correlation measures for non-continuous random variables. J. Multivariate Anal. 98(3):544–567.Crossref, Google Scholar
• Nikoloulopoulos A (2013) Copula-based models for multivariate discrete response data. Jaworski P, Durante F, Härdle W, eds. Copulae in Mathematical and Quantitative Finance, Lecture Notes in Statistics, vol. 213 (Springer, Berlin), 231–249.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff D (2017) The stochastic vehicle routing problem, a literature review, part II: Solution methods. EURO J. Transportation Logist. 6(4):349–388.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff D (2018) The stochastic vehicle routing problem, a literature review, part I: Models. EURO J. Transportation Logist. 7(3):193–221.Crossref, Google Scholar
• Panagiotelis A, Czado C, Joe H (2012) Pair copula constructions for multivariate discrete data. J. Amer. Statist. Assoc. 107(499):1063–1072.Crossref, Google Scholar
• Panagiotelis A, Czado C, Joe H, Stöber J (2017) Model selection for discrete regular vine copulas. Comput. Statist. Data Anal. 106:138–152.Crossref, Google Scholar
• Plackett R (1954) A reduction formula for normal multivariate integrals. Biometrika 41(3/4):351–360.Crossref, Google Scholar
• Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. Preprint, submitted August 13, https://arxiv.org/abs/1908.05659.Google Scholar
• Rai H, Verlinde S, Macharis C (2021) Unlocking the failed delivery problem? Opportunities and challenges for smart locks from a consumer perspective. Res. Transportation Econom. 87:100753.Crossref, Google Scholar
• Rajabi-Bahaabadi M, Shariat-Mohaymany A, Babaei M, Vigo D (2021) Reliable vehicle routing problem in stochastic networks with correlated travel times. Oper. Res. 21:299–330.Crossref, Google Scholar
• Rostami B, Desaulniers G, Errico F, Lodi A (2021) Branch-price-and-cut algorithms for the vehicle routing problem with stochastic and correlated travel times. Oper. Res. 69(2):436–455.Link, Google Scholar
• Schaefer J, Figliozzi M (2021) Spatial accessibility and equity analysis of Amazon parcel lockers facilities. J. Transportation Geography 97:103212.Crossref, Google Scholar
• Sklar M (1959) Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ. Paris 8:229–231.Google Scholar
• Smith M, Khaled M (2012) Estimation of copula models with discrete margins via Bayesian data augmentation. J. Amer. Statist. Assoc. 107(497):290–303.Crossref, Google Scholar
• Song P (2007) Correlated Data Analysis: Modeling, Analytics, and Applications (Springer-Verlag, New York).Google Scholar
• Stewart W, Golden B (1983) Stochastic vehicle routing: A comprehensive approach. Eur. J. Oper. Res. 14(4):371–385.Crossref, Google Scholar
• Sungur I, Ren Y, Ordóñez F, Dessouky M, Zhong H (2010) A model and algorithm for the courier delivery problem with uncertainty. Transportation Sci. 44(2):193–205.Link, Google Scholar
• Tang H, Miller-Hooks E (2004) Approximate procedures for probabilistic traveling salesperson problem. Transportation Res. Rec. 1882(1):27–36.Crossref, Google Scholar
• Tang H, Miller-Hooks E (2007) Solving a generalized traveling salesperson problem with stochastic customers. Comput. Oper. Res. 34(7):1963–1987.Crossref, Google Scholar
• Tillman F (1969) The multiple terminal delivery problem with probabilistic demands. Transportation Sci. 3(3):192–204.Link, Google Scholar
• Toriello A, Haskell W, Poremba M (2014) A dynamic traveling salesman problem with stochastic arc costs. Oper. Res. 62(5):1107–1125.Link, Google Scholar
• Van Duin J, De Goffau W, Wiegmans B, Tavasszy L, Saes M (2016) Improving home delivery efficiency by using principles of address intelligence for B2C deliveries. Transportation Res. Procedia 12:14–25.Crossref, Google Scholar
• Van Loon P, Deketele L, Dewaele J, McKinnon A, Rutherford C (2015) A comparative analysis of carbon emissions from online retailing of fast moving consumer goods. J. Cleaner Production 106:478–486.Crossref, Google Scholar
• Voccia S, Campbell A, Thomas B (2013) The probabilistic traveling salesman problem with time windows. EURO J. Transportation Logist. 2(1–2):89–107.Crossref, Google Scholar
• Xiao Q, Zhou S (2019) Matching a correlation coefficient by a Gaussian copula. Commun. Statist. Theory Methods 48(7):1728–1747.Crossref, Google Scholar
• Zhang M, Qin J, Yugang Y, Liang L (2018) Traveling salesman problems with profits and stochastic customers. Internat. Trans. Oper. Res. 25(4):1297–1313.Crossref, Google Scholar