Submodular Dispatching with Multiple Vehicles

References

• Banerjee D, Erera A, Toriello A (2022) Fleet sizing and service region partitioning for same-day delivery systems. Transportation Sci. 56(5):1327–1347.Link, Google Scholar
• Banerjee D, Erera A, Stroh A, Toriello A (2023) Who has access to e-commerce and when? Time-varying service regions in same-day delivery. Transportation Res. Part B: Methodological 170:148–168.Crossref, Google Scholar
• Beardwood J, Halton J, Hammersley J (1959) The shortest path through many points. Math. Proc. Cambridge Philos. Soc. 55(4):299–327.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Bogunovic I, Mitrović S, Scarlett J, Cevher V (2017) Robust submodular maximization: A non-uniform partitioning approach. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (JMLR.org, Sydney, Australia), 508–516.Google Scholar
• Carlsson JG, Liu S, Salari N, Yu H (2021) Provably good region partitioning for on-time last-mile delivery. Oper. Res. 72(1):91–109. Google Scholar
• Dell’Amico M, Iori M, Martello S, Monaci M (2008) Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS J. Comput. 20(3):333–344.Link, Google Scholar
• Desrosiers J, Lübbecke M (2006) A primer in column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 1–32.Google Scholar
• Erazo I, Toriello A (2024) Optimizing the trade-off between batching and waiting: Subadditive dispatching. Oper. Res. 73(6):3359–3388.Link, Google Scholar
• Erazo I, Toriello A (2025) Submodular dispatching with multiple vehicles. https://doi.org/10.1287/ijoc.2024.0886.cd, https://github.com/INFORMSJoC/2024.0886.Google Scholar
• Fowler JW, Mönch L (2022) A survey of scheduling with parallel batch (p-batch) processing. Eur. J. Oper. Res. 298(1):1–24.Crossref, Google Scholar
• Franceschetti A, Jabali O, Laporte G (2017) Continuous approximation models in freight distribution management. TOP 25(3):413–433.Crossref, Google Scholar
• Garey M, Johnson D (1978) “Strong” NP-completeness results: Motivation, examples, and implications. J. ACM 25(3):499–508.Crossref, Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Ghalami L, Grosu D (2019) Scheduling parallel identical machines to minimize makespan: A parallel approximation algorithm. J. Parallel Distributed Comput. 133:221–231.Crossref, Google Scholar
• Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, Berlin).Crossref, Google Scholar
• Habiba H, Hassam A, Sari Z, Amine CM, Souad T (2019) Minimizing makespan on identical parallel machines. 2019 Internat. Conf. Appl. Automation Industrial Diagnostics (ICAAID), vol. 1 (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Herer Y, Penn M (1995) Characterizations of naturally submodular graphs: A polynomially solvable class of the TSP. Proc. Amer. Math. Soc. 123(1995):673–679.Google Scholar
• Hirayama T, Liu Y, Makino K, Shi K, Xu C (2023) A polynomial time algorithm for finding a minimum 4-partition of a submodular function. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1680–1691.Google Scholar
• Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• Klapp MA, Erera AL, Toriello A (2018a) The one-dimensional dynamic dispatch waves problem. Transportation Sci. 52(2):402–415.Link, Google Scholar
• Klapp MA, Erera AL, Toriello A (2018b) The dynamic dispatch waves problem for same-day delivery. Eur. J. Oper. Res. 271(2):519–534.Crossref, Google Scholar
• Klapp MA, Erera AL, Toriello A (2020) Request acceptance in same-day delivery. Transportation Res. Part E: Logist. Transportation Rev. 143:102083.Crossref, Google Scholar
• Kramer A, Iori M, Lacomme P (2021) Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization. Eur. J. Oper. Res. 289(3):825–840.Crossref, Google Scholar
• Krause A, Golovin D (2014) Submodular function maximization. Bordeaux L, Hamadi Y, Kohli P, eds. Tractability: Practical Approaches to Hard Problems (Cambridge University Press, Cambridge, UK), 71–104.Crossref, Google Scholar
• Kuruvilla A, Paletta G (2015) Minimizing makespan on identical parallel machines. Internat. J. Oper. Res. Inform. Systems 6(1):19–29.Crossref, Google Scholar
• Lu S, Ma C, Liu X, Pardalos PM (2024) Scheduling identical serial-batching machines in the engine manufacturing supply chain by an integrated variable neighborhood search algorithm. Comput. Oper. Res. 164:106552.Crossref, Google Scholar
• Mönch L, Fowler J, Dauzère-Pérès S, Mason S, Rose O (2011) A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Scheduling 14:583–599.Crossref, Google Scholar
• Muter I (2020) Exact algorithms to minimize makespan on single and parallel batch processing machines. Eur. J. Oper. Res. 285(2):470–483.Crossref, Google Scholar
• Nemhauser G, Wolsey L (1999) Integer and Combinatorial Optimization (John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Ozturk O, Espinouse ML, Mascolo MD, Gouin A (2012) Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates. Internat. J. Production Res. 50(20):6022–6035.Crossref, Google Scholar
• Pessan C, Néron E (2011) Setup tasks scheduling during production resettings. Internat. J. Production Res. 49(22):6787–6811.Crossref, Google Scholar
• Pessoa AA, Bulhões T, Nesello V, Subramanian A (2022) Exact approaches for single machine total weighted tardiness batch scheduling. INFORMS J. Comput. 34(3):1512–1530.Link, Google Scholar
• Petris M, Archetti C, Cattaruzza D, Ogier M, Semet F (2024) A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem. Networks 84(4):446–464.Crossref, Google Scholar
• Schaller JE (2014) Minimizing total tardiness for scheduling identical parallel machines with family setups. Comput. Indust. Engrg. 72:274–281.Crossref, Google Scholar
• Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Schutten M, Van De Velde S, Zijm W (1996) Single-machine scheduling with release dates, due dates and family setup times. Management Sci. 42:1165–1174.Link, Google Scholar
• Snyder K (2024) 35 top e-commerce statistics. Forbes (March 28), https://www.forbes.com/advisor/business/ecommerce-statistics/.Google Scholar
• Statista (2023a) Global same-day delivery market size. Accessed November 20, 2025, https://www.statista.com/statistics/1255427/same-day-delivery-market-size-worldwide/.Google Scholar
• Statista (2023b) Retail e-commerce sales worldwide. Accessed November 20, 2025, https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/.Google Scholar
• Stroh AM, Erera AL, Toriello A (2022) Tactical design of same-day delivery systems. Management Sci. 68(5):3444–3463.Link, Google Scholar
• Trindade RS, Araújo O, Fampa M (2020) Arc-flow approach for parallel batch processing machine scheduling with non-identical job sizes. Baïou M, Gendron B, Günlük O, Mahjoub AR, eds. Combin. Optim. ISCO 2020, Lecture Notes in Computer Science, vol. 12176 (Springer, Cham, Switzerland), 179–190.Google Scholar
• Trindade RS, Araújo O, Fampa M, Müller F (2018) Modelling and symmetry breaking in scheduling problems on batch processing machines. Internat. J. Production Res. 56(22):7031–7048.Crossref, Google Scholar
• U.S. Census Bureau (2019) Census explorer. Accessed November 20, 2025, https://data.census.gov/.Google Scholar
• Vanelslander T, Deketele L, Hove D (2013) Commonly used e-commerce supply chains for fast moving consumer goods: Comparison and suggestions for improvement. Internat. J. Logist. 16(3):243–256.Crossref, Google Scholar
• Wang S, Zhou T, Lavania C, Bilmes JA, Ranzato M, Beygelzimer A, Dauphin Y, Liang P, Vaughan JW (2021) Constrained robust submodular partitioning. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 2721–2732.Google Scholar
• Wölck M, Meisel S (2022) Branch-and-price approaches for real-time vehicle routing with picking, loading, and soft time windows. INFORMS J. Comput. 34(4):2192–2211.Link, Google Scholar