Project R-6407

Dial-a-ride problems with real-life characteristics (Research)

This research proposal aims to improve current algorithms for solving complex, real-life variants of the diala- ride problem (DARP). The DARP is a generalization of a number of vehicle routing problems, but differs due to the human perspective. Passengers specify transportation requests, consisting of an origin location, a destination and a desired pickup or delivery time. Service level criteria, like a maximum time deviation and a maximum ride time, increase the complexity. Moreover, different user types and a heterogeneous vehicle fleet are often observed. Efficient algorithms, considering real-life characteristics, are necessary to safeguard the service level and cost efficiency. In the first part of my doctoral research, the human perspective is taken into account as a separate objective function, leading to a multi-objective problem. Decision makers don't need to define quality preferences in advance. They choose a posteriori among a set of non-dominated transportation plans, generated by means of an evolutionary algorithm. Pareto-based methods will be used to obtain preliminary information about the characteristics of the solution set and will be integrated in a hybrid metaheuristic approach. Attention will be given on how to adapt algorithmic components in order to exploit the underlying structure of the DARP. The solution methods will be tested on benchmark and real-life data. Algorithmic performance may be assessed using Pareto-compliant quality indicators, like the hypervolume indicator and the unary epsilon indicator. The second objective of this research proposal aims to quantify the potential for reduced operating costs and increased service level when engaging in a horizontal cooperation between two or more dial-a-ride (DAR) service providers. They may exchange customer requests or share vehicle capacity. Concretely, this requires the extension to the multi-depot case of the methods mentioned earlier on. The benefits of various degrees of cooperation will be examined under different problem conditions and benchmark data sets will be set up. In the third part of my doctoral research, the DARP is studied in a dynamic context, where new requests are revealed during the execution of the routes. In this case, the decision should be taken whether such request is accepted and the initial solution needs to be adapted in real time. It may also respond to unforeseen events, such as cancellations of requests, traffic delays or vehicle breakdowns. In this research proposal a policy will be developed as a guideline for planners. Firstly, an insertion heuristic will be applied to decide whether new requests will be served and local search operators will be developed to repair the initial solution. Secondly, a hybrid solver, integrating exact and heuristic optimization techniques, will be created to obtain a high-speed algorithm for generating new solutions. Finally, an experimental design and a multilevel regression analysis will be applied to determine which parameter settings and algorithmic components work best, depending on the problem characteristics. The experience with vehicle routing problems of the research group Logistics, in which this PhD proposal is situated, provides a thorough basis for these challenging objectives. The research group also participates in an Interuniversity Attraction Pole, in which it is responsible for the application of newly proposed solution procedures in distribution logistics. This PhD proposal matches perfectly with the scientific work in progress and will benefit from the expertise and research synergies acquired.

01 October 2015 - 30 September 2017