Steven Miltenburg: Fixed Order Routing 16 May 2024 16:00 - 17:00

We consider a routing problem with multiple identical vehicles, where instead of being able to determine the order in which locations (requests) are visited, there is a global fixed order. The challenge is thus to decide which requests are visited by which vehicles, as the order determines the order in which the vehicle has to visit these requests. We consider multiple objectives: to minimize the total traversed distance with a vehicle capacity c, to minimize the largest route C_max with at most k vehicles and the sum of completion times of the requests, Sum C_j with at most k vehicles. Counter-intuitively, this fixed order can make the problem harder. We show that on a line, where the problem is can be solved optimally without an order, it is strongly NP-hard with an order for the C_max and Sum C_j objectives. We also give a PTAS for the total distance objective on the line, though NP-completeness is not yet proven.
Furthermore we give some results on general metric spaces, where TSP without an order or capacity is already APX-hard. For the fixed order total distance objective, we give an approximation algorithm and show that the problem is both NP-hard and APX-hard, showing that our approximation bound is of the right order.