You are here

Dikas George

2008 Diploma Thesis Title:

A Toolkit for the Optimal Vehicle Routing Problem with Time Windows and Capacity Constraints

CV ( Greek Version)

 

Abstract

In this thesis we develop a toolkit to obtain efficient solutions for the Vehicle Routing Problem with Time Windows and Capacity Constraints (VRPTW) This toolkit has been based on the work of Larsen (2001) and Chabrier (2005) and has implemented the following methods / algorithms proposed in these references:
a) A Linear Programming Algorithm that uses the revised simplex method
b) A Column Generation Technique for linear problems
c) A Dynamic Labeling Algorithm for the Shortest Path Problem with additional
    constraints
d) A Branch and Bound Algorithm to obtain integer solutions.

These techniques are used in the following framework originally proposed by Larsen (2001): To obtain a good lower bound, the integrality constraints are relaxed, and the resulting general linear problem is divided in two separate problems; the Master Problem and the Sub-problem. The first one is formulated as a Set Partitioning Problem and it is solved through the revised simplex method. The dual (shadow) prices produced by this problem are sent to the sub-problem. The latter is formulated as an Elementary Shortest Path Problem with Time Windows and Capacity Constraints (ESPPTWCC). It is solved through a dynamic labeling algorithm. The sub-problem provides the necessary new columns (routes) to be inserted to the master problem, which is then, solved again. The final solution obtained by this iterative procedure is a good lower bound of the original integer problem. In order to obtain integer solutions, the aforementioned methods have been incorporated in a branch and bound scheme, which calls them iteratively to obtain the optimal (or a near optimal) solution.

 
The unified Branch and Bound and Column Generation framework used is called “Branch and Price via Column Generation”. The shadow prices produced by the solution of the linear problem are considered to be a “weighting” factor of the network arcs, and they affect the selection of the proposed routes (columns) by the sub-problem. In the Column Generation technique not all the feasible routes have to be known in advance since routes (columns) will be created from the solution procedure. This is a strong advantage of the proposed method, which achieves an efficient solution to large-scale problems within reasonable computational time.

The methods proposed by Larsen (2001) guarantee optimality for problems of appropriate complexity. In large scale problems, however, the computational complexity may be prohibitive. In these cases, key in obtaining the optimum is the “intelligent” guidance of the column generation method in selecting the next appropriate column to be inserted in the linear program. This aspect is further analyzed in the present thesis, by testing two labeling techniques that “accelerate” the solution of the ESPPTWCC problem. All the related experiments were performed using the Solomon Benchmark problems and compared against optimal solutions provided in the literature, and / or against an exhaustive search algorithm. Analytical results for the behavior of the proposed method, solution quality and computational complexity, are presented and discussed.
People: