2018/02/17 by Matheus Nohra Haddad, Rafael Martinelli, Haddad, Matheus Nohra +11
Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Transportation and Mobility Innovations #Urban and Freight Transport Logistics #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1802.06318
openalex publication_date 2018/02/17 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We consider the multi-vehicle one-to-one pickup and delivery problem with\nsplit loads, a NP-hard problem linked with a variety of applications for bulk\nproduct transportation, bike-sharing systems and inventory re-balancing. This\nproblem is notoriously difficult due to the interaction of two challenging\nvehicle routing attributes, "pickups and deliveries" and "split deliveries".\nThis possibly leads to optimal solutions of a size that grows exponentially\nwith the instance size, containing multiple visits per customer pair, even in\nthe same route. To solve this problem, we propose an iterated local search\nmetaheuristic as well as a branch-and-price algorithm. The core of the\nmetaheuristic consists of a new large neighborhood search, which reduces the\nproblem of finding the best insertion combination of a pickup and delivery pair\ninto a route (with possible splits) to a resource-constrained shortest path and\nknapsack problem. Similarly, the branch-and-price algorithm uses sophisticated\nlabeling techniques, route relaxations, pre-processing and branching rules for\nan efficient resolution. Our computational experiments on classical\nsingle-vehicle instances demonstrate the excellent performance of the\nmetaheuristic, which produces new best known solutions for 92 out of 93 test\ninstances, and outperforms all previous algorithms. Experimental results on new\nmulti-vehicle instances with distance constraints are also reported. The\nbranch-and-price algorithm produces optimal solutions for instances with up to\n20 pickup-and-delivery pairs, and very accurate solutions are found by the\nmetaheuristic.\n