Summary
Milk runs are an important transportation concept, e.g. in the automotive industry. Trucks start from a depot, pick up goods at different suppliers, and deliver those goods to a single customer. Therefore, milk runs are technically a pick up and delivery problem with multiple pick ups and a single delivery. They make it possible to deliver small lots eficiently and thus lower average inventory levels. Prerequisite is that there are several frequent orders from suppliers that are closely located, otherwise transshipment centers will be used in spite of handling costs. Pickup&Delivery problems calculate routes for single days, sometimes with the additional restriction of time windows for delivery. Models and algorithms for these problems exist and can help in practice as leadtimes are usually very short, in most cases only one day. It has been discussed whether it would be better to allow for delivery windows of a few days so that carriers have more leeway for route optimization (cf. [1]). Now the routing problem is extended with the problem of allocating orders to days. The integrated solution requires vehicles to make multiple trips and is formulated as the VRP with Multiple Trips (VRPM). The VRPM has found only little attention so far: “Although in practice multiple route assignment is common, there is a shortage of papers covering this feature.”[2] It is even more interesting to look at the problem from a dynamic point of view, i.e. to iterate through the days and to assign incoming orders to days without having information on future orders.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Pape, U. (2006) Agentenbasierte Umsetzung eines SCM-Konzepts zum Liefermanagement in Liefernetzwerken der Serienfertigung. HNI-Verlagsschriftenreihe, Paderborn
Petch, RJ, Salhi, S. (2004) A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Applied Mathematics 133:69–92
Brandão, JCS, Mercer, A. (1998) The multi-trip vehicle routing problem. Journal of the Operational Research Society 49:799–805
Azi, N., Gendreau, M., Potvin, J.-Y. (2007) An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European Journal of Operational Research 178:755–766
Azi, N., Gendreau, M., Potvin, J.-Y. (2007) An Exact Algorithm for a Vehicle Routing Problem with Time Windows and Multiple Use of Vehicles. Tristan VI, Phuket Island, Thailand
Zhao, QH, Wang, SY, Lai, KK, Xia, GP (2002) A vehicle routing problem with multiple use of vehicles. Advanced Modeling and Optimization 4:21–40
Taillard, ED, Laporte, G., Gendreau, M. (1996) Vehicle Routing with Multiple Use of Vehicles. Journal of the Operational Research Society 47:1065–1071
Salhi, S., Petch, R. J. (2007) A GA Based Heuristic for the Vehicle Routing Problem with Multiple Trips. Journal of Mathematical Modelling and Algorithms 6:591–613
Allulli, L., Ausiello, G., Laura, L. (2005) On the Power of Lookahead in On-Line Vehicle Routing Problems. Proceedings of the 11th Annual International Conference COCOON 2005, Kunming, China, Springer-Verlag
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Böhle, C., Dangelmaier, W. (2009). Milk Run Optimization with Delivery Windows and Hedging Against Uncertainty. In: Fleischmann, B., Borgwardt, KH., Klein, R., Tuma, A. (eds) Operations Research Proceedings 2008., vol 2008. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00142-0_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-00142-0_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00141-3
Online ISBN: 978-3-642-00142-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)