A mixed integer programming model for a continuous move transportation problem with service constraints
DOI:
https://doi.org/10.29105/rinn7.13-2Keywords:
Genetic Algorithms, Logistics Routing, Metaheuristics, Scheduling, Time WindowsAbstract
We consider a Pickup and Delivery Vehicle Routing Problem (PDP) commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple vehicle types available to cover a set of pickup and delivery requests, each of which has pickup time windows and delivery time windows. Transportation orders and vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which vehicle types. In addition we include some dock service
capacity constraints as is required on common real world operations. This problem requires to be attended on large scale instances (orders ≥ 500), (vehicles ≥ 150). As a generalization of the traveling salesman problem, clearly this problem is NP-hard. The exact algorithms are too slow for large scale instances. The PDP-TWDS is both a packing problem (assign order to
vehicles), and a routing problem (find the best route for each vehicle). We propose to solve the problem in three stages. The first stage constructs initials solutions at aggregate level relaxing some constraints on the original problem. The other two stages imposes time windows and dock service constraints. Our results are favorable finding good quality solutions in relatively short computational times.
Downloads
References
Applegate, D; Bixby, R; Chvátal, V. (1998). On the solution of traveling salesman problems, Documenta Mathematica Extra Volume ICM III, USA.
Ascheuer, N; Fischetti, M; Grotschel, M. (2001). Solving ATSP with time windows by branchand-cut, Springer-Verlag, Germany.
Cook, W; Rich, Jennifer. (1999). A parallel cutting-plane algorithm for the vehicle routing problem with time windows, Computational and Applied Mathematics Rice University, Houston USA.
Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P., Vigo, D. (2007). “Vehicle Routing", Transportation, Handbooks in Operations Research and Management Science,
Volume 14, C. Barnhart and G. Laporte (eds), Elsevier, Amsterdam, 367-428.
Dumas, Y., Desrosiers, J. & Soumis, F.(1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54, 7-22.
Dumas, Y; Desrosiers, J; Solomon, M. (1995). An algorithm for the traveling salesman problem with time windows, Operations Research 43(2), USA, pp. 23-25.
Desrosiers, J., Dumas, Y., Solomon, M.M., & Soumis, F. (1995). Time constrained routing and scheduling. In: M.O. Ball, T.L. Magnanti, C.L. Monma, & G.L. Nemhauser (eds.), Network
Routing, Handbooks in Operations Research and Management Science, vol. 8 (pp. 35-139). INFORMS: Elsevier Science.
Dessouky, Lu, Zhao, Leachman. (2006). "An Exact Solution Procedure for Determining the Optimal Dispatching Times for Complex Rail Networks," IIE Transactions 38, 141-152.
Fisher, R. (1995). The Design of Experiments, Hafner Press & Macmillan Publishers, London England, pp. 25-50.
Mitrovic, Snezana. (1998). Pickup and Delivery Problem with Time Windows, Technical Report SFU CMPT TR 1998-12, Canada, pp 38-39.
Palmgren, Myrna. (2001). A Column Generation Algorithm for the Log Truck Scheduling Problem, Department of Science and Technology (ITN), Linköping University, Norrköping Sweden, pp 3.
Ropke, S., Cordeau, J.-F., Laporte, G. (2007). "Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with
Time Windows", Networks 49, 258-272.
Savelsberg, M. (1995). Local search in Routing Problem with Time Windows, Annals of Operations Research, Rotherdam, the Netherlands, pp. 1-7.
Savelsbergh, Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29(1), 17-29.
Savelsbergh, M.W.P. & Sol, M.(1998). DRIVE: Dynamic routing of independent vehicles. Operations Research, 46(4), 474-490.
Solomon, M. (1984). On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints, Report 83-05-03, The Wharton School, USA.
Tsitsiklis, J. (1992). Special cases of traveling salesman and repairman problems with time windows, Networks No. 22, US
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 Innovaciones de Negocios
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
The InnOvaciOnes de NegOciOs magazine is a free and open access electronic magazine of a scientific-academic nature and is a publication of the Autonomous University of Nuevo León, in which the authors retain their copyright and grant the magazine the exclusive right to first publication of the work. Third parties are allowed to use the published content, as long as the authorship of the work is acknowledged and the first publication in this journal is cited.
For more information, please contact the Research Secretary (FACPyA) of the Autonomous University of Nuevo León. Telephone: (81) 1340-4430. Email: revinnova@uanl.mx
