A Tabu Search Heuristic for the Vehicle Routing Problem with Soft time Windows

Taillard, Éric; Badeau, Philippe; Gendreau, Michel; Guertin, François; Potvin, Jean-Yves
May 1997
Transportation Science;May97, Vol. 31 Issue 2, p170
Academic Journal
This paper describes a tabu search heuristic for the vehicle routing problem with soft time windows. In this problem, lateness at customer locations is allowed although a penalty is incurred and added to the objective value. By adding large penalty values, the vehicle routing problem with hard time windows can be addressed as well. In the tabu search, a neighborhood of the current solution is created through an exchange procedure that swaps sequences of consecutive customers (or segments) between two routes. The tabu search also exploits an adaptive memory that contains the routes of the best previously visited solutions. New starting points for the tabu search are produced through a combination of routes taken from different solutions found in this memory. Many best-known solutions are reported on classical test problems.


Related Articles

  • VEHICLE ROUTING. Bodin, Lawrence // Encyclopedia of Operations Research & Management Science;2001, p865 

    The entry provides information on vehicle routing. Determining the minimum cost set of routes for a fleet of identical vehicles is the traditional vehicle routing problem. The vehicles are to service a set of locations. Each location has a known demand for service. For such kinds of problems...

  • Driver's Workload Comparison in Waste Collection Vehicle Routing Problem. Benjamin, Aida Mauziah; Abdul-Rahman, Syariza // AIP Conference Proceedings;2016, Vol. 1782 Issue 1, p1 

    This paper compares the workload of the drivers for a waste collection benchmark problem. The problem involves ten data sets with different number of customers to be served and different number of disposal facilities available. Previous studies proposed a heuristic algorithm, namely Different...

  • ABOUT METHODS TO RESOLVE CREATIVE PROBLEMS. Leparov, Michail N. // Journal of International Scientific Publications: Materials, Met;2011, Vol. 5 Issue 3, p125 

    Problems, that cannot be formalized and for what no methods to solve them are known, are called heuristic problems. There are a lot of ways through what their solving is assisted. The objective of the present work is to propose any new approaches to solve heuristic problems.

  • METHOD "METAPHORS" TO RESOLVE CREATIVE PROBLEMS. Leparov, Michail N. // Journal of International Scientific Publications: Materials, Met;2011, Vol. 5 Issue 3, p137 

    Tasks which can not be formalized and for which there are no known methods for solving are called heuristic tasks. In most cases there are to be solved by usage of solutions of tasks which have already been made and the intelligence of the person who solves them. There are various methods which...

  • The Design of a Hierarchical Transportation Network with Transshipment Facilities. Current, John R. // Transportation Science;Nov88, Vol. 22 Issue 4, p270 

    In this paper an integer linear program is formulated to identify the least cost two-level hierarchical network. This network must include a primary path from a predetermined starting node to a predetermined terminus node. In addition, each node not on the primary path must be connected to some...

  • Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem. Ahuja, R. K.; Murty, V. V. S. // Transportation Science;Aug87, Vol. 21 Issue 3, p163 

    Network design problems have been widely investigated in the literature. In this paper, we study one such design problem, known as the Optimum Communication Spanning Tree (OCST) problem. We develop an exact algorithm based on the branch and bound approach and a heuristic algorithm to solve the...

  • A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem. Hertz, Alain; Mittaz, Michel // Transportation Science;Nov2001, Vol. 35 Issue 4, p425 

    The undirected capacitated are routing problem (CARP)arises naturally in several applications where streets require maintenance, or customers located along road must be serviced. Basic algorithmic procedures have recently been developed for the design of heuristics in an arc routing context....

  • BOUNDS AND HEURISTICS FOR CAPACITATED ROUTING PROBLEMS. Haimovich, M.; Rinnooy Kan, A. H. G. // Mathematics of Operations Research;Nov85, Vol. 10 Issue 4, p527 

    In a capacitated muting problem, the objective is to minimize the total distance travelled by vehicles of limited capacity to serve a set of customers that arc located in the Euclidean plane. We develop asymptotically optimal bounds and heuristics for this problem, under the assumption that the...

  • Unfreeze - Change - Refreeze: A Model for Heuristic Analysis. Zajchowski, Chris // Avalanche Review;Dec2011, Vol. 30 Issue 2, p28 

    The author discusses a model for heuristic analysis that skiers can follow. Models that are helpful in submitting potential heuristic and environmental factors to memory are discussed, including "Look, Listen, and Feel," by Kent McBride and "The Change Model," by Kurt Lewin. According to the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics