Technical Report - A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones
Now available for Download.
Drones have started to play an increasing role in logistic systems in both, academic research and practical context. In particular, drones have already been applied in various public and private service sectors including energy, agriculture, and emergency response. Recently, the Vehicle Routing Problem with Drones (VRPD) has been introduced as a variant of the Vehicle Routing Problem. In the case of the VRPD, a fleet of vehicles, each of them equipped with a set of drones, is tasked with delivering parcels to customers. The objective consists in designing feasible routes with minimal mission time. The drones may be launched from and retrieved by the vehicles and move at a velocity that might differ from the vehicle's speed. Furthermore, drones possess a limited fight endurance and small carrying capacity. The VRPD can be formulated as a Mixed Integer Linear Program (MILP) and, consequently, be solved by any standard MILP solver. With the aim of improving the performance of solvers, we introduce some sets of valid inequalities. Additionally, due to limited performance of the solvers in addressing large-scale instances, we address this issue by proposing an algorithm based on the well-known Variable Neighborhood Search (VNS) approach. In order to evaluate the performance of the introduced algorithm as well as the solver in solving the VRPD instances, we carried out extensive computational experiments.
Technical Report - An adaptive large neighborhood search with path relinking for a class of vehicle-routing problems with simultaneous pickup and delivery
now available for download
We study a class of vehicle-routing problems (VRP) with simultaneous pickup and delivery (VRPSPD). In VRPSPDs, each customer may require a certain quantity of goods delivered from the depot and a quantity of goods to be picked up and returned to the depot. Besides the standard VRPSPD, we address (i) the VRPSPD with time limit (VRPSPDTL), which imposes a time limit on the routes of the transportation vehicles, (ii) the VRPSPD with time windows (VRPSPDTW), which takes customer time windows into account, (iii) the VRP with divisible deliveries and pickups (VRPDDP), which allows for fullling the delivery and pickup requests of each customer in two separate visits, and (iv) the previously unstudied VRPDDP with time windows (VRPDDPTW). We develop a hybrid heuristic solution method which combines an adaptive large neighborhood search algorithm with a path relinking approach, called ALNS-PR, and we demonstrate the competitiveness of our algorithm on benchmark instances proposed in the literature.
Research areas and current projects
Our research focuses on modeling complex (and often stochastic) search and optimization problems in business, and solving them via computational heuristics. A special emphasis is given to distributed problems arising in social multi-agent systems, which cannot be optimized by pure economic price coordination. Imposing a solution by a central planner will often be rejected by the autonomous agents. We therefore need to design distributed mechanisms providing incentives to participate to the individual agents without deviating too much from a pareto-efficient solution.
We apply these methods to various domains, leading the following complementary areas of research::
- Computational Intelligence
- Vehicle Routing
- Yield Management and Planning of Internal Processes
- Multi-Agent Systems
- Recommender Systems for Reciprocal Matching
- Medical Data Mining and Forecasting
For details please refer to "Research".
Besides our Bachelor courses "Business Information Systems" and "Operations Research" we offer the following Master courses: