Abstract
The Vehicle Routing Problem with Pickups and Deliveries (VRPPD) arises in many application contexts and has been intensively studied in the last decades. We investigate the special case where pickup and delivery locations are distributed on a line. Although this situation is frequent when handling material in manufacturing systems with rectilinear layout, this case has not received enough attention so far. Derived from a real application, our general model also features load/unload times, vehicle capacities and the absence of a depot. A two-stage MIP-based heuristic that exploits such a special topology is devised, and its performance is assessed within an industrial case study provided by a large semiconductor manufacturer. We first compare our method to a standard Clarke and Wright type heuristic, then document its practical impact when implemented in a dynamic environment.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arbib, C., Ranjbar, F.K., Smriglio S.: A dynamic dial-a-ride model for optimal vehicle routing in a wafer fab. In: Proceedings of the 10th International Conference on Operations Research and Enterprise System, Online Streaming, 4–6 February 2021, pp. 281–286 (2021)
Berbeglia, G., Cordeau, J.F., Gribkovskaia, I., Laporte, G.: Static pickup and delivery problems: a classification scheme and survey. TOP 16, 1–31 (2007). https://doi.org/10.1007/s11750-007-0009-0
Burkard, R., Derigs, U.: The bottleneck matching problem. In: Assignment and Matching Problems: Solution Methods with FORTRAN-Programs. Lecture Notes in Economics and Mathematical Systems, vol. 184, pp. 60–71. Springer, Berlin-Heidelberg (1980). https://doi.org/10.1007/978-3-642-51576-7_5
Calik, H., Labbé, M., Yaman, H.: p-center problems. In: Laporte, G., Nickel, S., da Gama, F.S. (eds.) Location Science, pp. 79–92. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-13111-5_4
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)
Croes, G.A.: A method for solving traveling salesman problems. Oper. Res. 6, 791–812 (1958)
Garfinkel, R.: An improved algorithm for the bottleneck assignment problem. Oper. Res. 19(7), 1747–1751 (1971)
Guan, D.J.: Routing a vehicle of capacity greater than one. Discrete Appl. Math. 81, 41–57 (1998)
Ho, S., Szeto, W., Huo, Y., Leung, J., Petering, M., Tou, T.: A survey of dial-a-ride problems: literature review and recent developments. Transp. Res. B 111, 395–421 (2018)
Pundir, P., Porwal, S., Singh, B.: A new algorithm for solving linear bottleneck assignment problem. J. Inst. Sci. Technol. 20(2), 101–102 (2015)
Ralphs, T., Kopman, L., Pulleyblank, W., Trotter, L.E.: On the capacitated vehicle routing problem. Math. Program. Ser. B 94, 343–359 (2003). https://doi.org/10.1007/s10107-002-0323-0
Vidal, T., Laporte, G., Matl, P.: A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286(2), 401–416 (2020)
Wang, F., Lim, A., Xu, Z.: The one-commodity pickup and delivery travelling salesman problem on a path or a tree. Networks 48(1), 24–35 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Arbib, C., Pizzuti, A., Ranjbar, F.K., Smriglio, S. (2022). A MIP-Based Heuristic for Pickup and Delivery on Rectilinear Layout. In: Parlier, G.H., Liberatore, F., Demange, M. (eds) Operations Research and Enterprise Systems. ICORES ICORES 2020 2021. Communications in Computer and Information Science, vol 1623. Springer, Cham. https://doi.org/10.1007/978-3-031-10725-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-10725-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-10724-5
Online ISBN: 978-3-031-10725-2
eBook Packages: Computer ScienceComputer Science (R0)