Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem // Branch-and-Price y generación heurística de columnas para el problema generalizado de rutas de trenes de carretera

Autores/as

  • Michael Drexl Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz Fraunhofer Centre for Applied Research on Supply Chain Services SCS, Nuremberg

Palabras clave:

Vehicle routing, transshipment, fleet planning, elementary shortest path problem with resource constraints, rutas de vehículos, trasbordo, planificación de flotas, problema del camino más corto con limitaciones de recursos

Resumen

The generalized truck-and-trailer routing problem (GTTRP) constitutes a unified model for vehicle routing problems with trailers and a fixed lorry-trailer assignment. The GTTRP is a generalization of the truck-and-trailer routing problem (TTRP), which itself is an extension of the well-known vehicle routing problem (VRP). In the GTTRP, the vehicle fleet consists of single lorries and lorry-trailer combinations. Some customers may be visited only by a single lorry or by a lorry without its trailer, some may also be visited by a lorry-trailer combination. In addition to the customer locations, there is another relevant type of location, called transshipment location, where trailers can be parked and where a load transfer from a lorry to its trailer can be performed.

In this paper, two mixed-integer programming (MIP) formulations for the GTTRP are presented. Moreover, an exact solution procedure for the problem, a branch-and-price algorithm, and heuristic variants of this algorithm are described. Computational experiments with the algorithms are presented and discussed. The experiments are performed on randomly generated instances structured to resemble real-world situations and on TTRP benchmark instances from the literature. The results of the experiments show that instances of realistic structure and size can be solved in short time and with high solution quality by a heuristic algorithm based on column generation.

------------------------------------

El problema generalizado de rutas de trenes de carretera (generalized truck-and-trailer routing problem, GTTRP) constituye un modelo unificado para problemas de rutas de vehículos con remolques y asignación fija camión-remolque. El GTTRP es una generalización del truck-and-trailer routing problem (TTRP), que es una extensión del conocido problema de rutas de vehículos (vehicle routing problem, VRP). En el GTTRP, la flota de vehículos consiste en camiones sin remolque (camiones solos) y trenes de carretera. Algunos clientes pueden ser visitados exclusivamente por un camión solo o un camión sin su remolque, otros pueden ser visitados también por un tren de carretera. Además de las ubicaciones de los clientes hay otro tipo de localización llamada ubicación de trasbordo. Allí los remolques pueden ser aparcados, y es posible efectuar un trasbordo de carga desde un camión a su remolque.

En este trabajo se presentan dos modelos de programación lineal entero mixto (MIP). Además, se describen un algoritmo exacto branch-and-price y variantes heurísticas de este algoritmo. Se presentan y analizan estudios computacionales con los algoritmos. Se usan problemas generados aleatoriamente, diseñados para semejar situaciones reales, y problemas TTRP de la literatura. Los resultados muestran que, utilizando un algoritmo heurístico basado en generación de columnas, se pueden resolver problemas de estructura y tamaño real en poco tiempo y con solución de alta calidad.

Descargas

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

Citas

R. Ahuja, T. Magnanti, and J. Orlin, "Network Flows", Prentice-Hall, Upper Saddle River, 1993.

A. Assad and B. Golden, "Arc Routing Methods and Applications", in: M. Ball, T. Magnanti, C. Monma, and G. Nemhauser (eds.), Network Routing, Handbooks in Operations Research and Management Science, vol. 8, Elsevier, Amsterdam, 1995, pp. 375-483.

C. Barnhart, E. Johnson, G. Nemhauser, M. Savelsbergh, and P. Vance, "Branch-and-Price: Column Generation for Solving Huge Integer Programs", Operations Research, vol. 46, 1998, pp. 316-329.

L. Bodin and L. Levy, "Scheduling of Local Delivery Carrier Routes for the United States Postal Service", in: M. Dror (ed.), Arc Routing: Theory, Solutions, and Applications, Kluwer, Boston, 2000, pp. 419-442.

N. Boland, J. Dethridge, and I. Dumitrescu, "Accelerated Label Setting Algorithms for the Elementary Resource Constrained Shortest Path Problem", Operations Research Letters, vol. 34, 2006, pp. 58-68.

J. Brunswicker, "Optimale Standort- und Tourenplanung für die Rohmilcherfassung eines Molkereibetriebes", Lit, Münster, 1986.

A. Chabrier, "Vehicle Routing Problem with Elementary Shortest Path Based Column Generation", Computers & Operations Research, vol. 33, 2006, pp. 2972-2990.

I. Chao, "A Tabu Search Method for the Truck and Trailer Routing Problem", Computers & Operations Research, vol. 29, 2002, pp. 33-51.

E. Choi and D. Tcha, "A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem", Computers & Operations Research, vol. 34, 2007, pp. 2080-2095.

G. Dantzig and J. Ramser, "The Truck Dispatching Problem", Management Science, vol. 6, 1959, pp. 80-91.

M. Daskin, "Network and Discrete Location", Wiley, New York, 1995.

G. Desaulniers, J. Desrosiers, I. Ioachim, M. Solomon, F. Soumis, and D. Villeneuve, "A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems", in: T. Crainic and G. Laporte (eds.), Fleet Management and Logistics, Kluwer, Boston, 1998, pp. 57-93.

M. Drexl, "On Some Generalized Routing Problems", Ph. D. Thesis, Faculty of Business and Economics, RWTH Aachen University, 2007.

M. Drexl, "Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem", Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, No. 1102, 2011.

M. Drexl, "Synchronization in Vehicle Routing - A Survey of VRPs with Multiple Synchronization Constraints", Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, No. 1103, 2011.

D. Feillet, P. Dejax, M. Gendreau, and C. Gueguen, "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to Some Vehicle Routing Problems", Networks, vol. 44, 2004, pp. 216-229.

R. Fukasawa, H. Longo, J. Lysgaard, M. Poggi de Aragão, M. Reis, E. Uchoa, and R. Werneck, "Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem", Mathematical Programming, Series A, vol. 106, 2006, pp. 491-511.

J. Gerdessen, "Vehicle Routing Problem with Trailers", European Journal of Operational Research, vol. 93, 1996, pp. 135-147.

B. Golden, S. Raghavan, and E. Wasil (eds.), "The Vehicle Routing Problem: Latest Advances and New Challenges", Operations Research/Computer Science Interfaces Series, vol. 43, Springer, New York, 2008.

A. Hoff, "Heuristics for Rich Vehicle Routing Problems", Ph. D. Thesis, Molde University College, 2006.

A. Hoff and A. Løkketangen, "A Tabu Search Approach for Milk Collection in Western Norway Using Trucks and Trailers", Molde University College, 2006.

A. Imai, E. Nishimura, and J. Current, "A Lagrangian Relaxation-Based Heuristic for the Vehicle Routing with Full Container Load", European Journal of Operational Research, vol. 176, 2007, pp. 87-105.

I. Ioachim, S. Gélinas, F. Soumis, and J. Desrosiers, "A Dynamic Programming Algorithm for the Shortest Path Problem with Time Windows and Linear Node Costs", Networks, vol. 31, 1998, pp. 193-204.

S. Irnich and G. Desaulniers, "Shortest Path Problems with Resource Constraints", in: G. Desaulniers, J. Desrosiers, and M. Solomon (eds.), Column Generation, Springer, New York, 2005, pp. 33-65.

S. Irnich and D. Villeneuve, "The Shortest Path Problem with Resource Constraints and k-Cycle Elimination for k≥3", INFORMS Journal on Computing, vol. 18, 2006, pp. 391-406.

M. Jepsen, B. Petersen, and S. Spoorendonk, "A Branch-and-Cut Algorithm for the Elementary Shortest Path Problem with a Capacity Constraint", Department of Computer Science, University of Copenhagen, No. 08/01, 2008.

N. Kohl, J. Desrosiers, O. Madsen, M. Solomon, and F. Soumis, "2-Path Cuts for the Vehicle Routing Problem with Time Windows", Transportation Science, vol. 33, 1999, pp. 101-116.

G. Laporte, "Location-Routing Problems", in: A. Assad and B. Golden (eds.), Vehicle Routing: Methods and Studies, Elsevier, Amsterdam, 1988, pp. 163-197.

G. Laporte, Y. Nobert, and S. Taillefer, "Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems", Transportation Science, vol. 22, 1988, pp. 161-172.

M. Lübbecke and J. Desrosiers, "Selected Topics in Column Generation", Operations Research, vol. 53, 2005, pp. 1007-1023.

S. Lin, V. Yu, and S. Chou, "Solving the Truck and Trailer Routing Problem Based on a Simulated Annealing Heuristic", Computers & Operations Research, vol. 36, 2009, pp. 1683-1692.

S. Lin, V. Yu, and S. Chou, "A Note on the Truck and Trailer Routing Problem", Expert Systems with Applications, vol. 37, 2010, pp. 899-903.

G. Nagy and S. Salhi, "Nested Heuristic Methods for the Location-Routeing Problem", Journal of the Operational Research Society, vol. 47, 1996, pp. 1166-1174.

G. Nagy and S. Salhi, "Location-Routing: Issues, Models and Methods", European Journal of Operational Research, vol. 177, 2007, pp. 649-672.

E. Prescott-Gagnon, G. Desaulniers, and L. Rousseau, "A Branch-and-Price-Based Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows", Networks, vol. 54, 2009, pp. 190-204.

G. Righini and M. Salani, "Symmetry Helps: Bounded Bi-Directional Dynamic Programming for the Elementary Shortest Path Problem with Resource Constraints", Discrete Optimization, vol. 3, 2006, pp. 255-273.

S. Røpke, "Heuristic and Exact Algorithms for Vehicle Routing Problems", Ph. D. Thesis, Department of Computer Science, University of Copenhagen, 2005.

M. Salani, "Branch-and-Price Algorithms for Vehicle Routing Problems", Ph. D. Thesis, Faculty of Mathematical, Physical and Natural Sciences, University of Milan, 2005.

S. Scheuerer, "Neue Tabusuche-Heuristiken für die logistische Tourenplanung bei restringierendem Anhängereinsatz, mehreren Depots und Planungsperioden", Ph. D. Thesis, Faculty of Business, Economics and Management Information Systems, University of Regensburg, 2004.

S. Scheuerer, "A Tabu Search Heuristic for the Truck and Trailer Routing Problem", Computers & Operations Research, vol. 33, 2006, pp. 894-909.

F. Semet, "A Two-Phase Algorithm for the Partial Accessibility Constrained Vehicle Routing Problem", Annals of Operations Research, vol. 61, 1995, pp. 45-65.

F. Semet and E. Taillard, "Solving Real-Life Vehicle Routing Problems Efficiently Using Tabu Search", Annals of Operations Research, vol. 41, 1993, pp. 469-488.

P. Toth and D. Vigo (eds.), "The Vehicle Routing Problem", SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.

R. Vahrenkamp, "Transportation Logistic in Rural Setting - The Case of Milk Collection", Department of Business and Economics, University of Kassel, No. 5/1989, 1989.

F. Vanderbeck, "On Dantzig-Wolfe-Decomposition in Integer Programming and Ways to Perform Branching in a Branch-and-Price Algorithm", Operations Research, vol. 48, 2000, pp. 111-128.

H. Williams, "Model Building in Mathematical Programming", Wiley, Chichester, 1999.

Publicado

2016-11-04

Cómo citar

Drexl, M. (2016). Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem // Branch-and-Price y generación heurística de columnas para el problema generalizado de rutas de trenes de carretera. Revista De Métodos Cuantitativos Para La Economía Y La Empresa, 12, Páginas 5 a 38. Recuperado a partir de https://www.upo.es/revistas/index.php/RevMetCuant/article/view/2100

Número

Sección

Artículos