A mixed integer programming model for a continuous move transportation problem with service constraints

Autores/as

  • J. Fabián López UANL

DOI:

https://doi.org/10.29105/rinn7.13-2

Resumen

Key words: Genetic algorithms, logistics routing, metaheuristics, scheduling, time windows

Abstract. 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.

Palabras claves. Algoritmos genéticos, logística de ruteo, metahurística, programación, ventana de horario

Resumen. En la solución de problemas combinatorios, es importante evaluar el costobeneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de producto y con restricciones de ventana de horario. En la práctica, dicho problema requiere ser atendido con instancias de gran escala (nodos ≥100). Existe un fuerte porcentaje de ventanas de horario activas (≥90%) y con factores de amplitud ≥75%. El  problema es NP-hard y por tal motivo la aplicación de un método de solución exacta para resolverlo en la práctica, está limitado por el tiempo requerido para la actividad de ruteo. Se propone un algoritmo genético especializado, el cual ofrece soluciones de buena calidad (% de optimalidad aceptables) y en tiempos de ejecución computacional que hacen útil su aplicación en la práctica de la logística. Para comprobar la eficacia de la propuesta algorítmica se desarrolla un diseño experimental el cual hará uso de las soluciones óptimas obtenidas mediante un algoritmo de ramificación y corte sin límite de tiempo. Los resultados son favorables.

Descargas

Los datos de descargas todavía no están disponibles.

Métricas

Cargando métricas ...

Citas

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. DOI: https://doi.org/10.1016/0377-2217(91)90319-Q

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. DOI: https://doi.org/10.1287/opre.43.2.367

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 DOI: https://doi.org/10.1016/S0927-0507(05)80106-9

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. DOI: https://doi.org/10.1080/074081791008988

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 DOI: https://doi.org/10.1002/net.20177

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. DOI: https://doi.org/10.1287/trsc.29.1.17

Savelsbergh, M.W.P. & Sol, M.(1998). DRIVE: Dynamic routing of independent vehicles. Operations Research, 46(4), 474-490. DOI: https://doi.org/10.1287/opre.46.4.474

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 DOI: https://doi.org/10.1002/net.3230220305

Descargas

Publicado

2017-12-07

Cómo citar

López, J. F. (2017). A mixed integer programming model for a continuous move transportation problem with service constraints. Innovaciones De Negocios, 7(13). https://doi.org/10.29105/rinn7.13-2