A framework for the vehicle routing problem with dynamically inserted intermediate stops and its application to the skip loader problem
The thesis will be supervised by an employee of PTV AG in Karlsruhe. The thesis will ideally be worked on directly in Karlsruhe. There, the work can be based on an existing code base can be used.
In the context of this thesis, a theoretical framework for VRP variants shall be developed which have the following in common: along a tour, in addition to order stops (e.g., pickup or delivery stops) have to be scheduled in order for the tour to be valid. In rare cases, more than one intermediate stop is made.
A problem with this feature is the skip loader problem. The skip loader is used to transport empty skips to customers. As a rule, full skips are taken away and immediately driven to a disposal site. The empty skip can then be dropped off at the next customer. The problem becomes more difficult due to the fact that there are skips in two sizes (different DIN), whereby each vehicle can transport both types of skips (homogeneous fleet). It is possible that an empty skip is first driven to a loading point, where another skip has to be loaded, in case the next customer requires a different type of skip. In this simple case, there is only one loading point (here, called a depot) and the vehicle has to drive there if the next customer requires a different type of skip than the one that is loaded.
In this thesis a theoretical framework will be developed to solve such problems. After implementing a solution procedure for the skip loader problem, the effectiveness will be investigated by means of generated test instances. Different problems with the above property should be solvable with the framework and discussed in the thesis (i.e., a simple variant of the EVRP and a simple variant of the truck-and-trailer problem).
If you are interested, please send an e-mail including your CV and transcript of records to firstname.lastname@example.org.
The Lin-Kernighan Neighborhood operator for the Vehicle Routing Problem with Time Windows
The Capacitated Vehicle Routing Problem (CVRP) deals with the task of meeting the demands of a set of customers with a fleet of vehicles at minimum cost. Each customer must be visited exactly once, vehicle routes start and end at the depot, and vehicle capacities must be respected. The VRP with Time Windows (VRPTW) is an extension of the CVRP which additionally requires that service at the customers is started within given time windows. Heuristic solution methods for the VRPTW are often based on local search: a starting solution generated by a construction heuristic is iteratively improved by the use of so-called neighborhood operators. The Lin-Kernighan neighborhood operator deletes and creates edges in a stepwise fashion such that the sum of the partial improvements remains positive.
In this master thesis, the Lin-Kernighan operator shall be integrated into a local search for the VRPTW. A generalized objective function is used, which allows constraint violations and handles them by means of penalty costs, thus enabling the search to consider infeasible solutions. The search with the LK operator is strongly accelerated by evaluating only those partial moves that have a positive effect on the cost function. The central question of the work is how potentially infeasible partial moves can be evaluated in the course of the search. Programming skills are beneficial for working on this topic.
If you are interested, please feel free to write an email to email@example.com.
Learning good starting solutions for local search algorithms
Local-search-based algorithms are widely used to solve vehicle routing problems (VRPs). Starting with an initial solution, the iterative application of so-called neighborhood operators modifies the solution until a local optimum is reached. To escape from these, metaheuristics that rely on local search often use some sort of diversification mechanism. Over the last decades, many different diversification methods have been developed, which, e.g., rely on randomized multi-starts or perturbation steps. Boyan and Moore (2000) introduced the idea of trying to learn good starting solutions by generating an evaluation function that predicts the outcome of a local search given a specific starting solution. They developed the so-called STAGE algorithm that alternates local search and learning steps. Features are thereby used to represent solutions in a compact fashion and serve as input to the evaluation function. Even though the STAGE algorithm has already been successfully applied to combinatorial optimization problems like the bin-packing problem, there is no application to VRPs yet.
The goal of this master thesis is to continue on previous work at the chair and to improve the performance of our version of the STAGE algorithm to solve multi-depot VRPs. Precisely, the following questions shall be addressed:
- Are there additional features beyond those we have investigated to characterize VRP solutions and how do they perform?
- Which neighborhood operators should be used to perform the local search? Which should be used to obtain good neighboring solutions according to the evaluation function?
- Which machine learning model should be used to realize the evaluation function (linear, polynomial regression, …)?
Programming skills are beneficial for working on this topic. If you are interested, please feel free to write an email to firstname.lastname@example.org.