Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
8-1-1985
Abstract
This dissertation presents a new algorithm for the Vehicle Routing Problem (VRP) based on the set partitioning approach. Given a depot, a number of delivery points (stops) with known demands, and the vehicles with given capacities, the problem is to find the set of most economical vehicle routes satisfying all demand. Each route originates and terminates at the depot and must be feasible with respect to the truck capacity. In the set partitioning approach, each route is represented by a binary column with elements 1 for stops visited on the routes and 0 for stops not visited. The obvious difficulty is that the number of feasible columns can be too large to enumerate. To avoid this difficulty, a column generation scheme has been developed to solve the LP relaxation of the set partitioning formulation. A linear approximation of the TSP (Traveling Salesman Problem) objective function has been used to derive a lowerbound for the column generation subproblem. Using this lowerbound the subproblem is solved by a branch and bound approach. A new insert1on based lowerbound for the TSP has been developed which is used to avoid solving the TSPs frequently in the branch and bound search. The LP relaxation of VRP is solved by using the column generation subproblem. Several new ideas have been introduced to improve the computational efficiency of this process. The convergence of the LP is accelerated by imposing artificial upperbounding constraints on the duals, and gradually relaxing them later. Heuristic solutions of the VRP obtained by other algorithms are used for a priori estimation of optimal duals. Starting the LP from this estimated solution cons1derably improves the convergence. The information in the optimal LP basis is used to construct heuristic and optimal integer solutions to VRP. The equivalence of set partitioning and set covering problems in the special case of VRP has been shown. Based on this equivalence, an algorithm has been developed to extract a set covering solution from columns in the LP basis. This solution is then converted into a set partitioning solution which turns out to be quite close to optimal. A procedure for obta1ning optimal solutions to the VRP has been developed based on a well-known theorem on set partitioning. The optimal dual variables are used to generate a relatively small set of columns which is guaranteed to contain the optimal solution. Problems of up to 30 stops have been solved optimally within reasonable CPU time. Despite its computational limitations, set partitioning approach appears to be the most suitable for real world VRP. Ways of incorporating most real world constraints and considerations in this approach have been discussed. Several ideas for designing set partitioning based heuristics are also presented along with the scope for further work in this direction.
Keywords
Operations research, Vehicle routing problem, Combinatorial optimization, Algorithms, Linear programming, Branch and bound algorithms, Traveling salesman problem, Heuristic algorithms
Publication Title
Dissertation, Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 566 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Agarwal, Yogesh Kumar, "A Set Partitioning Approach to the Vehicle Routing Problem" (1985). Research Reports from the Department of Operations. 517.
https://commons.case.edu/wsom-ops-reports/517