Advanced Heuristics in Transportation and Logistics

Christos D. Tarantilis

Michel Gendreau

Diomidis Spinellis

 

You are required to plan the routes of your company’s 250 delivery trucks from your company’s 12 depots to the city’s 5000 vendor locations.  Traffic patterns, accidents and breakdowns, vendor-specified delivery time windows, perishable goods, returned empty packages, and product shortages at specific depots further complicate the picture.  And, by the way, yesterday’s plan is no longer applicable, because heavy snowfall overnight has invalidated your estimations of the trucks’ speeds; you need a new plan by daybreak, in two hours.  Where do you start?

In today’s global transportation and logistics environment, industries require computational and simulation-based methods that will lead to faster transactions, reduced operating costs, and improved performance and customer service. They also want methods and tools that provide more control and flexibility in their operations such as production and location planning, warehousing, distribution, and transportation.

Transportation and logistics organizations often face large-scale combinatorial problems on both operational and strategic levels. In such problems, all possible combinations of decisions and variables must be examined to find a solution; consequently, no partial enumeration-based exact algorithm can consistently solve them. This occurs because sharp lower bounds on the objective value are hard to derive, thus causing a slow convergence rate [1]. By exploiting problem-specific characteristics, classical heuristic methods, such as constructive and iterative local search methods, aim at a relatively limited exploration of the search space, thereby producing acceptable-quality solutions in modest computing times.

As a major departure from a classical heuristic, a metaheuristic method implies a higher-level strategy controlling a lower-level heuristic method. Metaheuristics exploit not only the problem characteristics but also ideas based on artificial intelligence methodologies, such as different types of memory structures and learning mechanisms, as well as analogies with optimization methods found in nature. Solutions produced by metaheuristics typically are of a much higher quality than those obtained with classical heuristic approaches, while their swift execution speed allows them to be used on combinatorial problems where a complete enumeration would be completely impractical.  Evidently, the success of the metaheuristic approaches arises from intelligent exploitation of the problem structure and the insight obtained by the effective interplay between intensification (concentrating the search into a specific region of the search space) and diversification (elaborating different regions in the solution space) mechanisms.

 

Metaheuristic Methods

We can classify metaheuristic algorithms using several different criteria [2]. A classification can be based on whether the metaheuristic algorithm works on a population of solutions at each iteration (such as Evolutionary Algorithms—EAs [3] and Adaptive Memory Procedures—AMPs [4]) or on a single solution (such as Annealing based Algorithms—AbAs [5], Tabu Search—TS [6], the Greedy Randomized Adaptive Search Procedure—GRASP [7], Iterated Local Search—ILS [8], Variable Neighborhood Search—VNS [9]) or on a learning mechanism (such as Neural Networks—NNs [10], Ant Algorithms—AAs [11]). An alternative classification can be based on the origins of the metaheuristic algorithm. This classification includes the Nature-inspired metaheuristics such as EAs, AAs and AbAs, and the non-Nature-inspired algorithms such as TS, ILS, VNS and GRASP. A further classification can be based on whether the algorithm employs a dynamic objective function (such as Guided Local Search—GLS [1]) or a static one. In addition, a metaheuristic algorithm can use one or various neighbor structures during the search process. Furthermore, a classification can be based on whether the metaheuristic uses memory (such as TS, AMPs, AAs) or not (such as AbAs, VNS). Finally, a general classification can be based on whether the method is a state-of-the-art metaheuristic algorithm or a sophisticated combination of concepts of different metaheuristics, a so called hybrid metaheuristic algorithm [12]. 

This Issue’s Papers

 

We were extremely fortunate to receive 62 papers for this special issue.  At the very least, this high number demonstrates the amount of active high-quality research that is performed worldwide in the area of this issue’s theme.  By the end we had enough material for at least three special issues.  As a result, the papers selected to appear here are only a representative sample of the use of metaheuristic strategies in transportation and logistics applications.

The special issue’s articles begin with the paper entitled “A Guided Cooperative Search for the Vehicle Routing Problem with Time Windows” by Le Bouthillier, Crainic and Kropf. This paper is a valuable contribution to the combinatorial optimization in the so-called guided cooperative search concept for solving the Vehicle Routing Problem with Time Windows. The computational effectiveness of the proposed methodology is confirmed by the results obtained on an extended set of benchmark problem sets from the literature.

The paper, “Case Study: An Intelligent Decision-Support System” by Z. Michalewicz, Schmidt, M. Michalewicz and Chiriac, reports a case study discussing the  design and the implementation of an Decision Support System for one of the world’s leading car manufacturers. The system generates profits in excess of $200 million per year by detecting data trends in a dynamic environment, and by employing sophisticated optimization and self-learning techniques.

Caricato and Grieco in their paper, “Using Simulated Annealing to Design a Material-Handling System”, present a Simulated Annealing algorithm to solve the design of a realistic guide path configuration for an AGV (Automated Guided Vehicles)-based material-handling system. Experimental results substantiate the efficiency of the proposed metaheuristic approach.

The paper, “A Hybrid Algorithm for Distribution Problems” by Bredstom, Ronnqvist and Carlsson presents a genetic algorithm, using linear programming models, for solving the problem of the distribution of pulp and route scheduling for vessels for one of the world’s largest pulp manufacturers. The proposed metaheuristic approach is also tested on the manufacturer’s real world case study.

Moura and Oliveira in their paper, “A GRASP Approach to the Container Loading Problem”, are also concerned with logistics decisions related with the packing of a set of boxes into a container, aiming at minimizing the wasted space. To solve this critical logistics problem, called Container Loading Problem, they develop a Greedy Randomized Adaptive Search Procedure (GRASP), which is also compared with other effective approaches extracted from the literature. The computational results obtained show that the proposed metaheuristic methodology is capable of producing high quality solutions.

The paper, “A Hybrid Approach to Designing Inbound Resupply Strategies” by Dullaert, Raa, Vernimmen and Witlox examines the problem of finding the best combination of sourcing alternatives that minimizes the total product costs (including product price, order, transportation and inventory costs) when goods are transported from a supplier to a receiver. The use of discrete event simulation within an evolutionary metaheuristic manages to model effectively stochastic variables and efficiently determine the reorder point. An application of the proposed methodology to a real-world case is also reported.

The final paper in this special issue, “Sequential and Parallel Path-Relinking Algorithms for the Quadratic Assignment Problem” by James, Rego and Glover examines one of the most challenging logistics problems of assigning a set of facilities to a set of locations, given the distances between the locations and the flows between the facilities. To solve this problem, known as Quadratic Assignment Problem, the authors develop both a sequential and a parallel version of a simplified yet effective Path Relinking algorithm. The proposed metaheuristic approach is tested on well-known benchmark instances, producing promising results.

Acknowledgements

 

The number of submissions required us to draw on the expertise of more than 150 reviewers, often with short deadlines.  Our thanks to all of them and especially to Chris T. Kiranoudis who ungrudgingly took more than his fair share of a reviewing burden.

References

 

1.        Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y. and Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society 53(5) 512–522.

2.        Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308.

3.        Calegari, P., Coray, G., Hertz, A., Kobler, D. and Kuonen, P. (1999). A taxonomy of evolutionary algorithms in combinatorial optimization. Journal of Heuristics 5(2) 145–158.

4.        Taillard, E.D., Gambardella, L.M., Gendreau, M. and Potvin, J.-Y. (2001). Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research 135(1) 1–16.

5.        Li, F., Golden, B. and Wasil, E. (2005). Very large-scale vehicle routing: New test problems, algorithms, and results. Computers & Operations Research 32(5) 1165–1179.

6.        Glover, F. and Laguna, M. (1997). Tabu search. Kluwer Academic Publishers.

7.        Festa, P. and Resende, M.G.C. (2002). GRASP: An annotated bibliography. In: Essays and surveys in metaheuristics. Eds.: C.C. Ribeiro and P. Hansen, pp. 325–367, Kluwer Academic Publishers.

8.        Lourenco, H. R., Martin, O. and Stutzle, T. (2002). Iterated local search. In: Handbook of Metaheuristics. Eds.: F. Glover and G. Kochenberger, pp. 321–353, Kluwer Academic Publishers.

9.        Hansen, P. and Mladenovic, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research 130(3) 449–467.

10.     Ghaziri, H. and Osman, I.H. (2003). A neural network algorithm for the traveling salesman problem with backhauls. Computers & Industrial Engineering 44(2) 267–281.

11.     Dorigo, M. and Stutzle T. (2004). Ant colony optimization. MIT Press.

12.     Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G. and Sormany, J.-S. (2004). New heuristics for the vehicle routing problem. In: Logistics systems: Design and optimization. Eds.: A. Langevin and D. Riopel, Kluwer Academic Publishers (to appear — earlier version as Technical Report G-2004-33, GERAD, Universite de Montreal, Canada).

 

Christos Tarantilis is a Lecturer in the Department of Management Science and Technology at the Athens University of Economics and Business. Contact him at tarantil@aueb.gr.

Michel Gendreau is Professor of Operations Research and Director of the Centre for Research on Transportation at Université de Montréal. Contact him at michelg@crt.umontreal.ca.

Diomidis Spinellis is an associate professor in the Department of Management Science and Technology at the Athens University of Economics and Business and the author of Code Reading: The Open Source Perspective (Addison-Wesley, 2003).  Contact him at dds@aueb.gr.