Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition

  • Original Research
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider the problem of scheduling a set of direct deliveries between a depot and multiple customers using a given heterogeneous truck fleet. The trips have time windows and weights, and they should be completed as soon after release as possible (minimization of maximum weighted flow time). Moreover, some trips can optionally be combined in predefined milk runs (i.e., round trip tours), which need not be linear combinations of the constituent direct trips, accounting, e.g., for consolidation effects because the loading dock needs to be approached only once. This problem has applications, e.g., in just-in-time, humanitarian, and military logistics. We adapt a mixed-integer programming model from the literature to this problem and show that deciding feasibility is NP-complete in the strong sense on three levels: assigning trips to trucks, selecting milk runs, and scheduling trips on each individual truck. We also show that, despite this complexity, a state-of-the-art constraint programming solver and a problem-specific approach based on logic-based Benders decomposition can solve even large instances with up to 175 trips in many cases, while the mixed-integer programming model is essentially unsolvable using commercial optimization software. We also investigate the robustness of the maximum flow time objective in the face of unforeseen delays as well as the influence of milk runs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. For example, for the formula \((x_0 \vee x_1 \vee x_2) \wedge (x_0 \vee \bar{x}_1 \vee \bar{x}_2) \wedge (\bar{x}_0 \vee x_1 \vee \bar{x}_2) \wedge (\bar{x}_0 \vee \bar{x}_1 \vee x_2)\), we get \(B_1 = \{\{5,1,2\}, \{5,1\}, \{5,2\}, \{5,3,4\}, \{5,3\}, \{5,4\}\}\), \(B_1 = \{\{6,1,3\}, \{6,1\}, \{6,3\}, \{6,2,4\}, \{6,2\}, \{6,4\}\}\), and \(B_3 = \{\{7,1,4\}, \{7,1\}, \{7,4\}, \{7,2,3\}, \{7,2\}, \{7,3\}\}\).

References

  • Al Theeb, N., Al-Araidah, O., & Aljarrah, M. H. (2019). Optimization of the heterogeneous vehicle routing problem with cross docking logistic system. Logistics Research, 12, 4.

    Google Scholar 

  • Anand, S., Bringmann, K., Friedrich, T., Garg, N., & Kumar, A. (2017). Minimizing maximum (weighted) flow-time on related and unrelated machines. Algorithmica, 77, 515–536.

    Article  Google Scholar 

  • Annouch, A., Bouyahyaoui, K., Bellabdaoui, A. (2016). A literature review on the full truckload vehicle routing problems. In 2016 3rd international conference on logistics operations management (GOL) (pp. 1–6). IEEE.

  • Bai, R., Xue, N., Chen, J., & Roberts, G. W. (2015). A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem. Transportation Research Part B: Methodological, 79, 134–148.

    Article  Google Scholar 

  • Ball, M. O., Golden, B. L., Assad, A. A., & Bodin, L. D. (1983). Planning for truck fleet size in the presence of a common-carrier option. Decision Sciences, 14, 103–120.

    Article  Google Scholar 

  • Barnes-Schuster, D., & Bassok, Y. (1997). Direct shipping and the dynamic single-depot/multi-retailer inventory system. European Journal of Operational Research, 101, 509–518.

    Article  Google Scholar 

  • Beck, J. C., Prosser, P., & Selensky, E. (2003). Vehicle routing and job shop scheduling: What’s the difference?. In ICAPS (pp. 267–276).

  • Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252.

    Article  Google Scholar 

  • Berman, P., Karpinski, M., & Scott, A. D. (2007). Computational complexity of some restricted instances of 3-SAT. Discrete Applied Mathematics, 155, 649–653.

    Article  Google Scholar 

  • Bertoli, F., Kilby, P., & Urli, T. (2018). Vehicle routing problems with deliveries split over days. Journal on Vehicle Routing Algorithms, 1, 1–17.

    Article  Google Scholar 

  • Bodin, L., & Golden, B. (1981). Classification in vehicle routing and scheduling. Networks, 11, 97–108.

    Article  Google Scholar 

  • Boysen, N., Emde, S., Hoeck, M., & Kauderer, M. (2015). Part logistics in the automotive industry: Decision problems, literature review and research agenda. European Journal of Operational Research, 242, 107–120.

    Article  Google Scholar 

  • Bunte, S., & Kliewer, N. (2009). An overview on vehicle scheduling models. Public Transport, 1, 299–317.

    Article  Google Scholar 

  • Cao, J. X., Lee, D. H., Chen, J. H., & Shi, Q. (2010). The integrated yard truck and yard crane scheduling problem: Benders’ decomposition-based methods. Transportation Research Part E: Logistics and Transportation Review, 46, 344–353.

    Article  Google Scholar 

  • Chen, L. (2008). Product & customer profiling for direct store delivery (DSD). Doctoral dissertation, Massachusetts Institute of Technology.

  • Codato, G., & Fischetti, M. (2006). Combinatorial Benders’ cuts for mixed-integer linear programming. Operations Research, 54, 756–766.

    Article  Google Scholar 

  • De Angelis, V., Mecoli, M., Nikoi, C., & Storchi, G. (2007). Multiperiod integrated routing and scheduling of World Food Programme cargo planes in Angola. Computers & Operations Research, 34, 1601–1615.

    Article  Google Scholar 

  • Emde, S., Polten, L., & Gendreau, M. (2020). Logic-based Benders decomposition for scheduling a batching machine. Computers & Operations Research, 113, 104777.

    Article  Google Scholar 

  • Emde, S., & Zehtabian, S. (2019). Scheduling direct deliveries with time windows to minimize truck fleet size and customer waiting times. International Journal of Production Research, 57, 1315–1330.

    Article  Google Scholar 

  • Gallego, G., & Simchi-Levi, D. (1990). On the effectiveness of direct shipping strategy for the one-warehouse multi-retailer R-systems. Management Science, 36, 240–243.

    Article  Google Scholar 

  • Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.

  • Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.

    Article  Google Scholar 

  • Grimes, D., Hebrard, E., Malapert, A. (2009). Closing the open shop: Contradicting conventional wisdom. In International conference on principles and practice of constraint programming (pp. 400–408). Springer, Berlin.

  • Gschwind, T., Irnich, S., Tilk, C., & Emde, S. (2020). Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network. Journal of Scheduling, 23, 363–377.

    Article  Google Scholar 

  • Held, M., & Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10, 196–210.

    Article  Google Scholar 

  • Holweg, M., & Miemczyk, J. (2003). Delivering the ‘3-day car’-the strategic implications for automotive logistics operations. Journal of purchasing and supply management, 9, 63–71.

    Article  Google Scholar 

  • Hong, S. C., & Park, Y. B. (1999). A heuristic for bi-objective vehicle routing with time window constraints. International Journal of Production Economics, 62, 249–258.

    Article  Google Scholar 

  • Hooker, J. (2000). Logic-based methods for optimization: Combining optimization and constraint satisfaction (Vol. 2). Wiley.

  • Hooker, J. N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55, 588–602.

    Article  Google Scholar 

  • Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 961, 33–60.

    Article  Google Scholar 

  • Hsu, C. I., Hung, S. F., & Li, H. C. (2007). Vehicle routing problem with time-windows for perishable food delivery. Journal of Food Engineering, 80, 465–475.

    Article  Google Scholar 

  • IBM. (2016). What’s in CPLEX Optimization Studio 12.7? Retrieved March 4, 2020 from https://developer.ibm.com/docloud/blog/2016/11/11/whats-in-cos-12-7/.

  • Kleywegt, A. J., Nori, V. S., & Savelsbergh, M. W. (2002). The stochastic inventory routing problem with direct deliveries. Transportation Science, 36, 94–118.

    Article  Google Scholar 

  • Kowalczyk, D., & Leus, R. (2017). An exact algorithm for parallel machine scheduling with conflicts. Journal of Scheduling, 20, 355–372.

    Article  Google Scholar 

  • Kutanoglu, E., & Mahajan, M. (2009). An inventory sharing and allocation method for a multi-location service parts logistics network with time-based service levels. European Journal of Operational Research, 194, 728–742.

    Article  Google Scholar 

  • Lam, E., Gange, G., Stuckey, P., Van Hentenryck, P., & Dekker, J. J. (2020). Nutmeg: a MIP and CP hybrid solver using branch-and-check. SN Operations Research Forum, 1(3). https://doi.org/10.1007/s43069-020-00023-2

  • Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19, 544–546.

    Article  Google Scholar 

  • Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.

    Article  Google Scholar 

  • Li, H., & Womer, K. (2009). Scheduling projects with multi-skilled personnel by a hybrid MILP/CP Benders decomposition algorithm. Journal of Scheduling, 12, 281–298.

    Article  Google Scholar 

  • Li, J. A., Wu, Y., Lai, K. K., & Liu, K. (2008). Replenishment routing problems between a single supplier and multiple retailers with direct delivery. European Journal of Operational Research, 190, 412–420.

    Article  Google Scholar 

  • Lin, L., Gen, M., & Wang, X. (2009). Integrated multistage logistics network design by using hybrid evolutionary algorithm. Computers & Industrial Engineering, 56, 854–873.

    Article  Google Scholar 

  • Lmariouh, J., El Hachemi, N., Jamali, A., Bouami, D., & Rousseau, L. M. (2019). An integrated production and distribution problem with direct shipment: A case from Moroccan bottled-water market. International Journal of Operational Research, 34, 144–160.

    Article  Google Scholar 

  • Malapert, A., Cambazard, H., Guéret, C., Jussien, N., Langevin, A., & Rousseau, L. M. (2012). An optimal constraint programming approach to the open-shop problem. INFORMS Journal on Computing, 24(2), 228–244.

    Article  Google Scholar 

  • Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29, 990–1001.

    Article  Google Scholar 

  • McCormack, I. M. (2014). The military inventory routing problem with direct delivery. MSc thesis, Air Force Institute of Technology, OH. https://scholar.afit.edu/etd/684

  • Meyer, A., & Amberg, B. (2018). Transport concept selection considering supplier milk runs-an integrated model and a case study from the automotive industry. Transportation Research Part E: Logistics and Transportation Review, 113, 147–169.

    Article  Google Scholar 

  • Mönch, L., Fowler, J. W., Dauzere-Peres, S., Mason, S. J., & Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14, 583–599.

    Article  Google Scholar 

  • Pinedo, M. (2015). Scheduling (5th ed.). Springer.

  • Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120, 228–249.

    Article  Google Scholar 

  • Queiser, H. (2007): Anlieferkonzepte in der Automobilindustrie – Ein internationaler Vergleich. Dokumentation – Zukunft AutomobilMontage. Retrieved February 25, 2020 from https://www.4flow.de/single-ansicht-news/article/anlieferkonzepte-in-der-automobilindustrie-ein-internationaler-vergleich.html

  • Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259, 801–817.

    Article  Google Scholar 

  • Saharidis, G. K., & Ierapetritou, M. G. (2013). Speed-up Benders decomposition using maximum density cut (MDC) generation. Annals of Operations Research, 210, 101–123.

    Article  Google Scholar 

  • Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35, 254–265.

    Article  Google Scholar 

  • Thorsteinsson, E. S. (2001). Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming. In International conference on principles and practice of constraint programming (pp. 16–30). Springer.

  • Tang, L., Jiang, W., & Saharidis, G. K. (2013). An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions. Annals of Operations Research, 210, 165–190.

    Article  Google Scholar 

  • Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: Problems, methods, and applications (2nd ed.). Society for Industrial and Applied Mathematics.

  • Tzur, M., & Drezner, E. (2011). A lookahead partitioning heuristic for a new assignment and scheduling problem in a distribution system. European Journal of Operational Research, 215, 325–336.

    Article  Google Scholar 

  • Verstichel, J., Kinable, J., De Causmaecker, P., & Berghe, G. V. (2015). A combinatorial Benders’ decomposition for the lock scheduling problem. Computers & Operations Research, 54, 117–128.

    Article  Google Scholar 

  • Xue, N., Bai, R., Qu, R., & Aickelin, U. (2021). A hybrid pricing and cutting approach for the multi-shift full truckload vehicle routing problem. European Journal of Operational Research, 292, 500–514.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CORAL—Cluster for Operations Research, Analytics, and Logistics, Department of Economics and Business Economics, Aarhus University, Fuglesangs Allé 4, 8210, Århus V, Denmark

    Simon Emde & Shohre Zehtabian

  2. Institut für Mathematik and Graduate School CE, Technische Universität Darmstadt, Darmstadt, Germany

    Yann Disser

Authors
  1. Simon Emde
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Shohre Zehtabian
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Yann Disser
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Simon Emde.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Emde, S., Zehtabian, S. & Disser, Y. Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition. Ann Oper Res 322, 467–496 (2023). https://doi.org/10.1007/s10479-022-04891-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-022-04891-1

Keywords