Pickup and Delivery Selection: Problem Formulation and Extension to Problem Variants
Abstract
Operational planning decisions of a carrier consist of accepting transport requests and constructing vehicle routes. However, a carrier has only a limited capacity within his own vehicle fleet and can only serve a selection of clients. Transport requests are accepted only if they contribute to a higher total profit. This practical aspect is modelled with the Pickup and Delivery with selection of customers. A mixed-integer programming formulation is given. It is indicated how the problem is solved by means of a meta-heuristic, more specifically a tabu-embedded simulated annealing algorithm. A number of alternative settings may appear in practice. They are discussed in this article.
Keywords: |
Heuristic algorithms; operations research; optimization; vehicle routing
|
Full Text: |
References
S. Mitrovic-Minic (1998). “Pickup and delivery problem with time windows: a survey,” Technical report TR1998-12, School of Computers Science, Simon Fraser University, Burnaby, BC, Canada. [Online]. Available: ftp://fas.sfu.ca/pub/cs/techreports/1998
S. Mitrovic-Minic and G. Laporte, “The pickup and delivery problem with time windows and transhipment,” INFOR, vol. 44, no. 3, 2006, pp. 217–227.
S.N. Parragh, K.F. Doerner and R.F. Hartl, “A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations,” Journal für Betriebswirtschaft, vol. 58, no. 2, 2008, pp. 81– 117. http://dx.doi.org/10.1007/s11301-008-0036-4
K. Ramaekers, A. Caris, G.K. Janssens and T. Maes, “Pickup and delivery selection with compulsory requests”. In: P.J. Sequeria Gonçalves (Ed.), Proceedings of the 11th Future Business Technology Conference (FUBUTEC’2015), Lisbon, Portugal, 27–29 April 2015, pp. 28–33, (ISBN978-90-77381-88-5).
C.-K. Ting and X.-L. Liao, “The selective pickup and delivery problem: formulation and a memetic algorithm,” International Journal of Production Economics, vol. 141, no. 1, 2013, pp. 199–211. http://dx.doi.org/10.1016/j.ijpe.2012.06.009
B. Verweij and K. Aardal, “The merchant subtour problem,” Mathematical Programming, vol. 94, no. 2–3, 2003, pp. 295–322. http://dx.doi.org/10.1007/s10107-002-0321-2
Y. Arda, Y. Crama and T. Pironet, “A profitable pickup and delivery problem with time windows,” ORBEL 22 (22nd National Conference of the Belgian Operations Research Society). Booklet of abstracts, Brussels, 26–28 Jan. 2008, pp. 76–77. [Online]. Available: http://orbel22.hallot.net/ docs/BookletORBEL22.pdf
T. Pironet, “The full truck-load profitable multi-vehicle one-to-one pick- up and delivery problem with hard time windows”, Thesis DEA en Sciences de Gestion, HEC-Management School, Liège University, Belgium, 2007.
L.F. Frantzeskakis and W.B. Powel, “A successive linear approximation procedure for stochastic, dynamic vehicle allocation problems,” Transportation Science, vol. 24, no. 1, 1990, pp. 40–57. http://dx.doi.org/10.1287/trsc.24.1.40
A.J. Kleywegt and J.D. Papastravou “Acceptance and dispatching policies for a distribution problem”. Transportation Science, vol. 32, 1998, pp. 127–141. http://dx.doi.org/10.1287/trsc.32.2.127
J. Schönberger, H. Kopfer and D. Mattfeld, “A combined approach to solve the pickup and delivery selection problem”, in Leopold- Wildburger, U., Rendl, F. and Wascher, G. (Eds.), Operations Research Proceedings 2002, pp. 150–155.
G. Desaulniers, J. Desrosiers, A. Erdmann, M.M. Solomon and F. Soumis, “VRP with pickup and delivery”., In: Toth P. and Vigo D. (Eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 2002, pp. 225–242. http://dx.doi.org/10.1137/1.9780898718515.ch9
H. Li and A. Lim, “A metaheuristic for the pickup and delivery problem with time windows,” in Proceedings of the 13th IEEE International Conference on Tools and Artificial Intelligence, Nov. 2001, Dallas TX, USA, pp. 160–167. http://dx.doi.org/10.1109/ictai.2001.974461
J. Schönberger, Operational Freight Carrier Planning, Springer, Berlin, 2005.
M. Ziebuhr and H. Kopfer, “The integrated operational transportation planning problems with compulsory requests,” in Gonzalez-Ramirez, R.G., Schulte, F., Voβ, S., Ceroni Diaz J.A., Proc. International Conference on Computational Logistics (ICCL2014), Lecture Notes in Computer Science 8760, 2014, pp. 1–15, Springer. http://dx.doi.org/10.1007/978-3-319-11421-7_1
H. Kopfer and X. Wang, “Combining vehicle routing with forwarding – extensions of the vehicle routing problem by different types of sub- contracting”. Journal of the Korean Institute of Industrial Engineers, vol. 35 no. 1, 2009, pp. 1–14.
M.-C. Bolduc, J. Renaud and F. Boctor, “A heuristic for the routing and carrier selection problem”. European Journal of Operational Research, vol. 183, 2007, pp. 926–932. http://dx.doi.org/10.1016/j.ejor.2006.10.013
A. Colorni and G. Righini, “Modeling and optimizing dynamic dial-a- ride problems,” International Transactions in Operational Research, vol. 8, 2001, pp. 155–166. http://dx.doi.org/10.1111/1475-3995.00256
Refbacks
- There are currently no refbacks.
Copyright (c) 2015 Katrien Ramaekers, An Caris, Tabitha Maes, Gerrit K. Janssens
This work is licensed under a Creative Commons Attribution 4.0 International License.