Premium
A two‐level local search heuristic for pickup and delivery problems in express freight trucking
Author(s) -
De Giovanni Luigi,
Gastaldon Nicola,
Sottovia Filippo
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21917
Subject(s) - tabu search , computer science , truck , heuristic , pickup , vehicle routing problem , revenue , operations research , service (business) , routing (electronic design automation) , local search (optimization) , variable neighborhood search , service level , mathematical optimization , level of service , transport engineering , metaheuristic , engineering , mathematics , business , algorithm , computer network , aerospace engineering , statistics , accounting , marketing , artificial intelligence , image (mathematics)
We consider a multiattribute vehicle routing problem inspired by a freight transportation company operating a fleet of heterogeneous trucks. The company offers an express service for requests including multiple pickup and multiple delivery positions spread in a regional area, with associated soft or hard time windows often falling in the same working day. Routes are planned on a daily basis and reoptimized on‐the‐fly to fit new requests, taking into account constraints and preferences on capacities, hours of service, route termination points. The objective is to maximize the difference between the revenue from satisfied orders and the operational costs. The problem mixes attributes from both intercity less‐than‐truckload and express couriers operations, and we propose a two‐level local search heuristic. The first level assigns orders to vehicles through a variable neighborhood stochastic tabu search; the second level optimizes the route service sequences. The algorithm, enhanced by neighborhood filtering and parallel exploration, is embedded in a decision support tool currently in use in a small trucking company. Results have been compared to bounds obtained from a mathematical programming model solved by column generation. Experience on the field and test on literature instances attest to the quality of results and the efficiency of the proposed approach.