1 March 2020 in Transportation Science
This work addresses a challenging inventory routing problem that arises from a practical application faced by air-product companies, including Air Liquide. Given its computational complexity and industrial importance, this problem (denoted as IRP-Challenge2016) was presented as the topic of the French Operational Research and Decision Support Society/European Operational Research Society (ROADEF/EURO) Challenge 2016. The IRP-Challenge2016 seeks an optimal delivery schedule to minimize the unit distribution cost, while satisfying various hard constraints. It involves a single product, a heterogeneous fleet, heterogeneous drivers, multiperiods, a deterministic consumption forecast, and time-window constraints. We present a new mathematical formulation of the problem and introduce a matheuristic algorithm that integrates a local search-based metaheuristic with mathematical programming. Our algorithm combines mixed integer programming and linear programming as slave methods to optimize timing and delivery and embeds these procedures within a multineighborhood search metaheuristic to adjust routes. The method extends and enhances a preliminary version of our algorithm, which ranked third in the final round of the ROADEF/EURO Challenge 2016. Computational results for 20 challenge benchmark instances demonstrate the value of the proposed algorithm in terms of both effectiveness and efficiency with respect to the results reported in the competition. We additionally analyze several key components of our matheuristic to gain an insight into its operation.
16 June 2021 in Computers & Operations Research
7 September 2023 in Expert Systems with Applications
23 November 2023 in Egyptian Informatics Journal
3 April 2019 in IEEE Access
The shortest simple path problem with must-pass nodes (SSPP-MPN) aims to find a minimum-cost simple path in a directed graph, where some specified nodes must be visited. We call these specified nodes as must-pass nodes. The SSPP-MPN has been proven to be NP-hard when the number of specified nodes is more than one, and it is at least as difficult as the traveling salesmen problem (TSP), a well-known NP-hard problem. In this paper, we propose a multi-stage metaheuristic algorithm based on multiple strategies such as k-opt move, candidate path search, conflicting nodes promotion, and connectivity relaxation for solving the SSPP-MPN. The main idea of the proposed algorithm is to transform the problem into the classical TSP by relaxing the simple path constraint and try to repair the obtained solutions in order to meet the demands of the original problem. Computational results tested on three sets of totally 863 instances and comparisons with reference algorithms show the efficacy of the proposed algorithm in terms of both solution quality and computational efficiency.
7 July 2025 in Engineering Applications of Artificial Intelligence