Abstract
This paper presents a multi-period vehicle routing problem for a large-scale production and distribution network. The vehicles must be routed in such a way as to minimize travel and inventory costs over a multi-period horizon, while also taking retailer demands and the availability of products at a central production facility into account. The network is composed of one distribution center and hundreds of retailers. Each retailer has its demand schedule representing the total number of units of a given product that should have been received on a given day. Many high value products are distributed. Product availability is determined by the production facility, whose production schedule determines how many units of each product must be available on a given day. To distribute these products, the routes of a heterogeneous fleet must be determined for a multiple period horizon. The objective of our research is to minimize the cost of distributing products to the retailers and the cost of maintaining inventory at the facility. In addition to considering product availability, the routing schedule must respect many constraints, such as capacity restrictions on the routes and the possibility of multiple vehicle trips over the time horizon. In the situation studied, no more than 20 product units could be carried by a single vehicle, which generally limited the number of retailers that could be supplied to one or two per route. This article proposes a mathematical formulation, as well as some heuristics, for solving this single-retailer-route vehicle routing problem. Extensions are then proposed to deal with the multiple-retailer-route situation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Achuthan N.R., Cacetta L. & Hill S.P. (2003) “An improved branch-and-cut algorithm for the capacitated vehicle routing problems.” Transportation Science, 37, 2: 153–169.
Blumenfeld D.E., Burns L.D. & Daganzo C.F. (1991) “Synchronizing production and transportation schedules.” Transportation Research Part B, 25, 23–37.
Burns L.D., Hall R.W., Blumenfeld D.E. & Daganzo C.F. (1985) “Distribution strategies that minimize transportation and inventory cost.” Operations Research, 33, 469–490.
Chandra P. & Fisher M.L. (1994) “Coordination of production and distribution planning.” European Journal of Operational Research, 72, 503–517.
Clark A.J. & Scarf H. (1960) “Optimal Policies for a Multi-Echelon Inventory Problem.” Management Science, 6, 475–490.
Clarke G. & Wright J.W. (1964) “Scheduling of vehicles from a central depot to a number of delivery points.” Operations Research, 12, 568–581.
Cordeau J.-F., Desaulniers G., Desrosiers J., Solomon M.M. & Soumis F. (2002) “VRP with time windows.” In The Vehicle Routing Problem, P. Toth & D. Vigo (ed.), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 157–193.
Cordeau J.-F., Gendreau M., Hertz A., Laporte G. & Sormany J.-S. (2005) “New heuristics for vehicle routing problem.” In “Logistics Systems: Design and Optimization” (A. Langevin & D. Riopel ed.), Kluwer, 279–297.
Erengüç, S.S., Simpson N.C. & Vakharia A.J. (1999) “Integrated production/distribution planning in supply chains: An invited review.” European Journal of Operational Research, 115, 219–236.
Gavirneni S. (2001) “Benefits of co-operation in a production distribution environment.” European Journal of Operational Research, 130, 612–622.
Gendreau M., Laporte G., Musaraganyi C. & Taillard E.D. (1999) “A tabu search heuristic for the heterogeneous fleet vehicle routing problem.” Computers & Operations Research, 26, 1153–1173.
Gendreau M., Laporte G. & Potvin J.-Y. (2002) “Metaheuristics for the capacitated vehicle routing problem.” In The Vehicle Routing Problem, P. Toth & D. Vigo (ed.), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 129–154.
Helsgaun K. (2000) “An effective implementation of the Lin-Kernighan traveling salesman heuristic.” European Journal of Operational Research, 126, 106–130.
Laporte G. (1992a) “The Traveling Salesman Problem: An overview of exact and approximate algorithms.” European Journal of Operational Research, 59, 231–247.
Laporte G. (1992b) “The Vehicle Routing Problem: An overview of exact and approximate algorithms.” European Journal of Operational Research, 59, 345–358.
Laporte G. (1993) “Recent algorithmic Developments for the traveling salesman problem and the vehicle routing problem.” Ricerca Operativa, 23, 68: 5–27.
Laporte G., Gendreau M., Potvin J.-Y. & Semet F. (2000) “Classical and modern heuristics for the vehicle routing problem.” International Transactions in Operational Research, 7, 285–300.
Laporte G. & Osman I.H. (1995) “Routing Problems: A Bibliography.” Annals of Operations Research, 61, 227–262.
Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. & Shmoys D.B. (1985) “The traveling salesman problem. A guided tour of combinatorial optimisation.” John Wiley & Sons.
Reimann M., Doerner K. & Hartl R.F. (2004) “D-Ants: Savings Based Ants divide and conquer the vehicle routing problems.” Computers and Operations Research, 31, 563–591.
Renaud J. & Boctor F.F. (2002) “A sweep-based algorithm for the fleet size and mix vehicle routing problem”. European Journal of Operational Research, 140, 618–628.
Tarantilis C.D., Kiranoudis C.T. & Vassiliadis V. S. (2004) “A threshold accepting metaheuristic for the heteregenous fixed vehicle routing problem.” European Journal of Operational Research, 152, 1: 148–158.
Thomas, D.J. & Griffin P.M. (1996) “Coordinated supply chain management.” European Journal of Operational Research, 94, 1–15.
Toth P. & Vigo D. (1998) Exact solution of the Vehicle Routing Problem”. Fleet Management and Logistics, T.G. Crainic & G. Laporte (ed.), Kluwer, Boston, 1–31.
Toth P. & Vigo D. (2002) “The Vehicle Routing Problem.” SIAM Monographs on Discrete Mathematics and Applications, P. Toth & D. Vigo (ed.), Philadelphia.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bolduc, MC., Renaud, J. & Montreuil, B. Synchronized routing of seasonal products through a production/distribution network. cent.eur.j.oper.res. 14, 209–228 (2006). https://doi.org/10.1007/s10100-006-0169-2
Issue Date:
DOI: https://doi.org/10.1007/s10100-006-0169-2