Search

This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality initial solutions are generated by means of a savings-based heuristic that combines diversification strategies with learning mechanisms. In Phase 2, an attempt is made to reduce the number of routes in the initial solution with a new local search procedure. In Phase 3, the solution from Phase 2 is further improved by a set of four local search operators that are embedded in a deterministic annealing framework to guide the improvement process. Some new implementation strategies are also suggested for efficient time window feasibility checks. Extensive computational experiments on the 168 benchmark instances have shown that the suggested method outperforms the previously published results and found 167 best-known solutions. Experimental results are also given for the new problem variant. [ABSTRACT FROM AUTHOR]

This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows (VRPTW).The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Metaheuristics are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in the first part of this article. In addition to describing basic features of each method, experimental results for Solomon's benchmark test problems are presented and analyzed. [ABSTRACT FROM AUTHOR]

This paper presents a survey of the research on the vehicle routing problem with time windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. Both traditional heuristic route construction methods and recent local search algorithms are examined. The basic features of each method are described, and experimental results for Solomon's benchmark test problems are represented and analyzed. Moreover,we discuss how heuristic methods should be evaluated and propose using the concept of Pareto optimality in the comparison of different heuristic approaches. The metaheuristic methods are described in the second part of this article. [ABSTRACT FROM AUTHOR]

Presents a deterministic metaheuristic approach based on a modification of the variable neighborhood search for the vehicle-routing problem with time windows. Creation of initial solution based on construction heuristics; Route-elimination procedure; Improvement of solutions using local-search procedures.