Beta 1


Title Taboo Search Based Metaheuristic for Solving Multiple Depot VRPPD with Intermediary Depots
Author Sigurjonsson, Karl
Supervisor Larsen, Jesper (Operations Research, Department of Management Engineering, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract This thesis presents a tabu search based metaheuristic to solve the Multiple Depot Vehicle Routing Problem with Pickup and Delivery and Intermediary Depots. The problem consists of scheduling routes for a fleet of homogeneous vehicles that pull trailers carrying freight containers. Each vehicle is based at a specific depot and can carry only one container at a time. Each container must be picked up and moved to its final destination. Along the way it is possible to drop the containers off at the various depots to be picked up at a later time, thus effectively splitting each container’s route into separate sections. The objective is to minimize the overall time needed to deliver all the containers. The metaheuristic developed explores solution neighbourhoods by means of two op- erations that work on the vehicle routes, routeleg substitution and routeleg splitting. A routeleg substitution removes one leg of a container’s route from a vehicle’s route and assigns it to another vehicle’s route. A split operation splits a container’s route on some intermediary depot, thus allowing each part to be assigned to different ve- hicles. A third operation, routeleg merge, is defined to make it possible to restore unproductive splits. An algorithm is implemented that attempts to combine these operations in an in- telligent way to produce feasible solutions to real life large scale data sets within a reasonable time frame. It alternates between iterations of routeleg substitutions and splits, always looking for the best neighbourhood solutions. Separate tabu lists for each of the three operations are maintained to prevent the algorithm from retracing its steps in the solution space. Certain infeasible solutions are allowed but penalized in the objective function. A simple method to dynamically control the severity of the penalty to encourage the algorithm into and subsequently force it out of infeasibility is explored. The final algorithm has various parameters that can be tuned, drastically effecting its effectiveness, both in solution quality and running time. Multiple test cases are presented to determine the performance of the algorithm over several different data sets to determine the optimal values for these parameters in relation to the size and characteristics of the data set.
Series IMM-M.Sc.-2008-103
Fulltext
Original PDF ep08_103.pdf (1.87 MB)
Admin Creation date: 2008-10-13    Update date: 2008-10-13    Source: dtu    ID: 224453    Original MXD