Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation … Read more

Integer programming formulations for the elementary shortest path problem

Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this … Read more

Solution Methods for the Multi-trip Elementary Shortest Path Problem with Resource Constraints

We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more