A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation

References

• Aardal K, Pochet Y, Wolsey LA (1995) Capacitated facility location: Valid inequalities and facets. Math. Oper. Res. 20(3):562–582.Link, Google Scholar
• Abdolmaleki M, Shahabi M, Yin Y, Masoud N (2019) Itinerary planning for cooperative truck platooning. Preprint, submitted November 14, http://dx.doi.org/10.2139/ssrn.3481598.Google Scholar
• Aguilera NE, Bianchi SM, Nasini GL (2004) Lift and project relaxations for the matching and related polytopes. Discrete Appl. Math. 134(1-3):193–212.Crossref, Google Scholar
• Atamtürk A (2003) On the facets of the mixed-integer knapsack polyhedron. Math. Programming 98:145–175.Google Scholar
• Atamtürk A, Küçükyavuz S, Tezel B (2017) Path cover and path pack inequalities for the capacitated fixed-charge network flow problem. SIAM J. Optim. 27(3):1943–1976.Crossref, Google Scholar
• Au YH, Tunçel L (2016) A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1):411–451.Crossref, Google Scholar
• Balas E (1997) A modified lift-and-project procedure. Math. Programming 79(1):19–31.Crossref, Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1-3):3–44.Crossref, Google Scholar
• Baldacci R, Battarra M, Vigo D (2009) Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks 54:178–189.Crossref, Google Scholar
• Bandelt HJ, Oosten M, Rutten JH, Spieksma FC (1999) Lifting theorems and facet characterization for a class of clique partitioning inequalities. Oper. Res. Lett. 24(5):235–243.Crossref, Google Scholar
• Baskar LD, Schutter BD, Hellendoorn H (2013) Optimal routing for automated highway systems. Transportation Res. Part C: Emerging Tech. 30:1–22.Crossref, Google Scholar
• Bergenhem C, Hedin E, Skarin D (2012) Vehicle-to-vehicle communication for a platooning system. Procedia Soc. Behav. Sci. 48:1222–1233.Crossref, Google Scholar
• Bhoopalam AK, Agatz N, Zuidwijk R (2018) Planning of truck platoons: A literature review and directions for future research. Transportation Res. Part B: Methodological 107:212–228.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2019) The price of discretizing time: A study in service network design. EURO J. Transportation Logistics 8(2):195–216.Crossref, Google Scholar
• Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1):13–26.Link, Google Scholar
• Boysen N, Briskorn D, Schwerdfeger S (2018) The identical-path truck platooning problem. Transportation Res. Part B: Methodological 109:26–39.Crossref, Google Scholar
• Burer S, Vandenbussche D (2006) Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3):726–750.Crossref, Google Scholar
• Castritius SM, Hecht H, Möller J, Dietz CJ, Schubert P, Bernhard C, Morvilius S, Haas CT, Hammer S (2020) Acceptance of truck platooning by professional drivers on German highways. A mixed methods approach. Appl. Ergonomics 85:103042.Crossref, Google Scholar
• Coelho LC, Laporte G (2014) Improved solutions for inventory-routing problems through valid inequalities and input ordering. Internat. J. Production Econom. 155(1):391–397.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer International Publishing, Cham, Switzerland).Google Scholar
• Contardo C, Desaulniers G, Lessard F (2015) Reaching the elementary lower bound in the vehicle routing problem with time windows. Networks 65(1):88–99.Crossref, Google Scholar
• Dantzig GB, Eaves BC (1973) Fourier-Motzkin elimination and its dual. J. Combin. Theory Ser. A 14(3):288–297.Crossref, Google Scholar
• Dey KC, Yan L, Wang X, Wang Y, Shen H, Chowdhury M, Yu L, Qiu C, Soundararaj V (2016) A review of communication, driver characteristics, and controls aspects of cooperative adaptive cruise control (CACC). IEEE Trans. Intelligent Transportation Systems 17(2):491–509.Crossref, Google Scholar
• Ferreira CE, Martin A, de Souza CC, Weismantel R, Wolsey LA (1996) Formulations and valid inequalities for the node capacitated graph partitioning problem. Math. Programming 74(3):247–266.Crossref, Google Scholar
• Fischer F, Helmberg C (2012) Dynamic graph generation for the shortest path problem in time expanded networks. Math. Programming 143(1-2):257–297.Crossref, Google Scholar
• Gade D, Küçükyavuz S, Sen S (2012) Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Programming 144(1):39–64.Google Scholar
• Gendreau M, Ghiani G, Guerriero E (2015) Time-dependent routing problems: A review. Comput. Oper. Res. 64:189–197.Crossref, Google Scholar
• Gong S, Shen J, Du L (2016) Constrained optimization and distributed computation based car following control of a connected and autonomous vehicle platoon. Transportation Res. Part B: Methodological 94:314–334.Crossref, Google Scholar
• Grötschel M, Wakabayashi Y (1990) Facets of the clique partitioning polytope. Math. Programming 47:367–387.Crossref, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh M (1998) Lifted cover inequalities for mixed 0-1 integer programs: Computation. INFORMS J. Comput. 10(4):427–437.Link, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh M (1999a) Lifted cover inequalities for mixed 0-1 integer programs: Complexity. INFORMS J. Comput. 11(1):117–123.Link, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MW (1999b) Lifted flow cover inequalities for mixed 0-1 integer programs. Math. Programming 85(3):439–467.Crossref, Google Scholar
• Gungor OE, Al-Qadi IL (2020) All for one: Centralized optimization of truck platoons to improve roadway infrastructure sustainability. Transportation Res. Part C: Emerging Tech. 114:84–98.Crossref, Google Scholar
• Huygens D, Labbé M, Mahjoub AR, Pesneau P (2006) The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut. Networks 49(1):116–133.Crossref, Google Scholar
• Jeroslow RG (1977) Cutting-plane theory: Disjunctive methods. Ann. Discrete Math. 1:293–330.Google Scholar
• Kılınç MR, Linderoth J, Luedtke J (2017) Lift-and-project cuts for convex mixed integer nonlinear programs. Math. Programming Comput. 9(4):499–526.Crossref, Google Scholar
• Kocuk B, Jeon H, Dey SS, Linderoth J, Luedtke J, Sun XA (2016) A cycle-based formulation and valid inequalities for DC power transmission problems with switching. Oper. Res. 64(4):922–938.Link, Google Scholar
• Koster AM, Kutschka M, Raack C (2011) Robust network design: Formulations, valid inequalities, and computations. Networks 61(2):128–149.Crossref, Google Scholar
• Küçükyavuz S (2012) On mixing sets arising in chance-constrained programming. Math. Programming 132(1):31–56.Crossref, Google Scholar
• Larson J, Liang KY, Johansson KH (2015) A distributed framework for coordinated heavy-duty vehicle platooning. IEEE Trans. Intelligent Transportation Systems 16(1):419–429.Crossref, Google Scholar
• Larson J, Munson T, Sokolov V (2016) Coordinated platoon routing in a metropolitan network. Gebremedhin AH, Boman EG, Ucar B, eds. 2016 Proc. Seventh SIAM Workshop Combin. Sci. Comput. (Society for Industrial and Applied Mathematics, Philadelphia), 73–82.Google Scholar
• Larsson E, Sennton G, Larson J (2015) The vehicle platooning problem: Computational complexity and heuristics. Transportation Res. Part C: Emerging Tech. 60:258–277.Crossref, Google Scholar
• Letchford AN (2001) On disjunctive cuts for combinatorial optimization. J. Combin. Optim. 5(3):299–315.Crossref, Google Scholar
• Li B (2017a) Stochastic modeling for vehicle platoons (I): Dynamic grouping behavior and online platoon recognition. Transportation Res. Part B: Methodological 95:364–377.Crossref, Google Scholar
• Li B (2017b) Stochastic modeling for vehicle platoons (II): Statistical characteristics. Transportation Rese. Part B: Methodological 95:378–393.Crossref, Google Scholar
• Liang KY, Mårtensson J, Johansson KH (2016) Heavy-duty vehicle platoon formation for fuel efficiency. IEEE Trans. Intelligent Transportation Systems 17(4):1051–1061.Crossref, Google Scholar
• Louveaux Q, Wolsey LA (2007) Lifting, superadditivity, mixed integer rounding and single node flow sets revisited. Ann. Oper. Res. 153(1):47–77.Crossref, Google Scholar
• Luo F, Larson J, Munson T (2018) Coordinated platooning with multiple speeds. Transportation Res. Part C: Emerging Tech. 90:213–225.Crossref, Google Scholar
• Nourmohammadzadeh A, Hartmann S (2016) The fuel-efficient platooning of heavy duty vehicles by mathematical programming and genetic algorithm. Martín-Vide C, Mizuki T, Vega-Rodríguez MA, eds. Theory and Practice of Natural Computing, Lecture Notes in Computer Science, vol. 10687 (Springer, Cham, Switzerland), 46–57.Google Scholar
• Oosten M, Rutten JHGC, Spieksma FCR (2001) The clique partitioning problem: Facets and patching facets. Networks 38(4):209–226.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Perboli G, Tadei R, Tadei R (2010) New families of valid inequalities for the two-echelon vehicle routing problem. Electronic Notes Discrete Math. 36(1):639–646.Crossref, Google Scholar
• Pochet Y, Wolsey LA (1993) Lot-sizing with constant batches: Formulation and valid inequalities. Math. Oper. Res. 18(4):767–785.Link, Google Scholar
• Richard J, de Farias Jr I, Nemhauser G (2003) Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithm. Math. Programming 98:89–113.Crossref, Google Scholar
• Schechter M (1998) Integration over a polyhedron: An application of the Fourier-Motzkin elimination method. Amer. Math. Monthly 105(3):246–251.Crossref, Google Scholar
• Serizawa K, Mikami M, Moto K, Yoshino H (2019) Field trial activities on 5G NR V2V direct communication toward application to truck platooning. 2019 IEEE 90th Vehicular Tech. Conf. (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Skutella M (2009) An introduction to network flows over time. Cook W, Lovász L, Vygen J, eds. Research Trends in Combinatorial Optimization (Springer, Berlin), 451–482.Google Scholar
• Sokolov V, Larson J, Munson T, Auld J, Karbowski D (2017) Platoon formation maximization through centralized routing and departure time coordination. Preprint, submitted January 5, https://arxiv.org/abs/1701.01391.Google Scholar
• Tsugawa S (2013) An overview on an automated truck platoon within the Energy ITS project. IFAC Proc. Volumes 46(21):41–46.Crossref, Google Scholar
• Tsugawa S, Jeschke S, Shladover SE (2016) A review of truck platooning projects for energy savings. IEEE Trans. Intelligent Vehicles 1(1):68–77.Crossref, Google Scholar
• van de Hoef S, Johansson KH, Dimarogonas DV (2015) Coordinating truck platooning by clustering pairwise fuel-optimal plans. 2015 IEEE 18th Internat. Conf. Intelligent Transportation Systems (IEEE, Piscataway, NJ), 408–415.Google Scholar
• Wang S, Li J, Mehrotra S (2022) A solution approach to distributionally robust chance-constrained assignment problems. INFORMS J. Optim. 4(2):125–147.Google Scholar
• Williams HP (1976) Fourier-Motzkin elimination extension to integer programming problems. J. Combin. Theory Ser. A 21(1):118–123.Crossref, Google Scholar
• Winder A (2016) “ITS4CV”—ITS for commercial vehicles. Report, ERTICO—ITS Europe, Brussels. http://erticonetwork.com/wp-content/uploads/2016/09/ITS4CV-Report-final-2016-09-09.pdf.Google Scholar
• Ye Q, Chen X, Liao R, Yu L (2019) Development and evaluation of a vehicle platoon guidance strategy at signalized intersections considering fuel savings. Transportation Res. Part D: Transport Environ. 77:120–131.Crossref, Google Scholar
• You J, Miao L, Zhang C, Xue Z (2020) A generic model for the local container drayage problem using the emerging truck platooning operation mode. Transportation Res. Part B: Methodological 133:181–209.Crossref, Google Scholar
• Zhang W, Jenelius E, Ma X (2017) Freight transport platoon coordination and departure time scheduling under travel time uncertainty. Transportation Res. Part E: Logistics Transportation Rev. 98:1–23.Crossref, Google Scholar
• Zhang J, Feng T, Yan F, Qiao S, Wang X (2020) Analysis and design on intervehicle distance control of autonomous vehicle platoons. ISA Trans. 100:446–453.Google Scholar