Algorithms and solutions to multi-level vehicle routing problems

In the famous classical Vehicle Routing Problem (VRP), a fleet of vehicles services a set of customers from a distribution depot to deliver or collect products. Each vehicle has a fixed capacity which cannot be exceeded and each customer has a known demand that must be fully satisfied. The objective is to provide each vehicle with a sequence of deliveries so that all customers are serviced and the total distance traveled by the fleet (or the total travel cost incurred by the fleet) is minimized without violating some other specified constraints. The Multi-level Vehicle Routing Problems (MLVRP) addressed in this dissertation contain at least two levels of decision making optimization in which the VRP is a specific level or a variant. However, the lowest level of the MLVRP is always a Traveling Salesman Problem (TSP) or a TSP-variant. The TSP is an NP-hard optimization problem, so the MLVRP's are at least as difficult as the TSP. For a large scale MLVRP, an exact method will be hard to get an optimal solution to the problem in a limited real world computation time. In the real world application, a heuristic method that can get a near optimal solution to the problem by using a reasonable computation time is preferred and practical. In this dissertation, five prototypes of the MLVRP are addressed. They are the orienteering problem, the team orienteering problem, the multi-depot vehicle routing problem, the period vehicle routing, and the period traveling salesman problem. For each type of problem, an effective heuristic method based upon a same simple basic idea is developed. The basic idea is that the algorithms accept some worse solutions when the searching procedure continues. When we make a decision of transitting a solution to another one, a set of candidates are considered one after one. Whenever a candidate can improve the objective function value, it is performed right away and all others are ignored. When no candidate can improve the objective function value, then one that losses the objective function value at the least will be performed if the amount of lossing value is not too many. The heuristics are implemented on the bench mark test problems taken from the literatures and the results are compared to those published along with the existing methods. A varieties of new test problems are also generated for each type of addressed MLVRP and are solved by the newly developed heuristics and by a new code of an existing methods or a carefully inspection. The comparisons for both sets of test problems for all five types of MLVRP show the superiority of the new heuristics. Finally, we synthesize the heuristics developed in this dissertation as a new general heuristic method for solving the MLVRP related optimization problems.