Source-linked AI summary
A matheuristic approach for the Pollution-Routing Problem
Raphael Kramer, Anand Subramanian, Thibaut Vidal, Lucídio dos Anjos Formiga Cabral
TL;DR
The paper addresses the Pollution-Routing Problem, where routes and vehicle speeds jointly determine environmental and operational costs under capacity and time-window constraints. It proposes ILS-SP-SOA, a hybrid of local search, set partitioning, and recursive speed optimization, and reports high-quality solutions that outperform previous methods across the PRP, FCVRP, and EMVRP settings.
Problem
The PRP requires coordinated routing and speed decisions because speed affects cost, travel time, emissions, and the set of feasible time-window routes.
Method
The paper combines Iterated Local Search, Set Partitioning, and a recursive Speed Optimization Algorithm to integrate route and speed decisions.
Results
The method generates high-quality solutions consistently and outperforms previous literature methods on the PRP, FCVRP, and EMVRP.
Takeaways & Limitations
The integrated matheuristic provides a competitive approach for green vehicle-routing problems involving environmental objectives and, for the PRP, time windows and speed decisions.
Takeaways & Limitations
Further work is needed to integrate speed decisions more tightly into local search because combined neighborhoods may be highly time-consuming.
Abstract
from arXiv · showhide
This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by [Bektas and Laporte (2011), Transport. Res. B-Meth. 45 (8), 1232-1250]. The objective is to minimize operational and environmental costs while respecting capacity constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. The vehicle speeds are considered as decision variables. They complement routing decisions, impacting the total cost, the travel time between locations, and thus the set of feasible routes. We propose a method which combines a local search-based metaheuristic with an integer programming approach over a set covering formulation and a recursive speed-optimization algorithm. This hybridization enables to integrate more tightly route and speed decisions. Moreover, two other "green" VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The proposed method compares very favorably with previous algorithms from the literature and many new improved solutions are reported.
1 Introduction
The paper addresses the Pollution-Routing Problem, where environmental and operational costs, capacity, and time windows interact with vehicle-speed decisions. It proposes a hybrid method that integrates routing and speed optimization through local search, set partitioning, and computational evaluation.
- Motivation: The Pollution-Routing Problem minimizes operational and environmental costs while respecting vehicle capacity and customer time windows.Its environmental costs are linked to fuel consumption and greenhouse-gas emissions.
- Challenge: Routing and speed decisions are tightly related, but previous methods optimized them sequentially.This separation can make it harder to coordinate feasible routes with appropriate speeds.
- Approach: The proposed algorithm combines Speed Optimization, Set Partitioning, and multi-start Iterated Local Search.The method is designed to integrate route and speed decisions through repeated optimization steps.
- Approach: The approach handles time-window constraints and evaluates local-search moves in amortized O(1) time.It also considers infeasible solutions during shaking and is tested on instances with both large and tight time windows.
2 Related works and challenges
Prior green-VRP research incorporated distance, load, congestion, road conditions, fuel, emissions, and speed into routing objectives. The PRP combines these concerns with time windows, creating conflicts between emissions, travel duration, and route feasibility.
- Prior green-VRP models: Earlier green-VRP models estimated environmental costs using distance, duration, road topography, congestion, vehicle load, or speed.These studies included formulations for CO2 reduction, energy minimization, and fuel consumption.
- PRP formulation: The PRP minimizes operational and environmental costs while considering distance, load per distance unit, speed, route duration, and customer time windows.It also introduced variants involving distance, weighted load, and energy minimization.
- Previous PRP methods: Previous PRP work used a two-phase heuristic that solved routing first and optimized vehicle speeds afterward.The reported approach used Adaptive Large Neighborhood Search followed by a recursive speed algorithm.
- Challenge: Higher speeds shorten routes but increase emissions, whereas lower speeds can reduce feasible routes and sometimes increase distance or emissions.The paper therefore seeks a better balance between routing and speed decisions.
3 Problem description
The PRP chooses routes and arc speeds for capacitated vehicles serving customers within time windows. Its objective combines fuel-consumption and driving costs, while the EMVRP and FCVRP provide simplified green-routing variants.
- PRP structure: The PRP is defined on a directed graph with a depot, capacitated vehicles, customer demands, service times, time windows, and arc distances.Routes must start and end at the depot, respect capacity, and serve every customer within its time window.
- PRP structure: Each arc speed is a decision variable bounded by v_min and v_max, and the solution jointly selects a speed matrix and customer routes.Speeds affect emissions, travel time, total cost, and time-window feasibility.
- Objective: The PRP objective combines fuel consumption priced per liter with driving costs priced per unit of time.The fuel model uses vehicle, network, and fuel-related parameters.
- Objective: The speed minimizing fuel cost and the speed minimizing fuel plus driver costs are defined separately in the PRP model.The latter includes driver wages and is used for travel-cost calculations.
- Related variants: The EMVRP uses distance and load×distance, while the FCVRP uses a linear fuel-per-distance function involving vehicle weight, carried load, and fixed vehicle cost.Neither variant includes PRP time-window or speed decisions.
4 The proposed ILS-SP-SOA matheuristic
ILS-SP-SOA combines iterated local search, speed optimization, and set-partitioning optimization for green vehicle routing with time windows. Its local search uses efficient route evaluation, while recursive speed optimization adjusts arc speeds to satisfy time-window constraints.
- Hybrid framework: ILS-SP-SOA is a matheuristic combining Iterated Local Search, Speed Optimization, and integer programming over a set-partitioning formulation.The hybrid procedure alternates heuristic search with exact optimization over generated routes.
- Hybrid framework: The method initializes speeds, constructs a solution, applies local search and speed optimization, updates route pools, and periodically invokes a MIP solver.Restarts and temporary or permanent route pools support repeated exploration and set-partitioning optimization.
- Local search: The local search uses randomized variable-neighborhood descent with inter-route and intra-route neighborhoods such as Shift, Swap, Reinsertion, Or-opt, Exchange, and 2-opt.These neighborhoods relocate, exchange, or reorder customers within or between routes.
- Local search: Time-window violations are temporarily allowed through time-warp penalties, and route moves are evaluated using concatenated subsequence data structures.The stored data include duration, time warp, load, distance, travel time, load×distance, and speed²×distance.
- Perturbation: Perturbations shift customers, merge routes, or change speeds, while capacity-infeasible moves are undone.Change Speeds is triggered after consecutive iterations without improvement.
- Speed optimization: The recursive speed algorithm optimizes speeds on fixed routes while respecting time windows, waiting times, driver wages, and non-fixed final arrival times.It identifies violations, splits the route recursively, and revises speeds after computing arrival times.
5 Computational Results
Experiments evaluate the proposed methods on PRP, FCVRP, and EMVRP benchmarks, including newly constructed tighter-time-window PRP sets. The dynamic method generally improves solution quality, while speed diversity and tighter time windows increase computational difficulty.
- PRP performance: The proposed methods largely outperform ALNS in solution quality and run 2–50 times faster, although the comparison uses different computing environments.The reported speed difference is therefore approximate rather than a controlled hardware comparison.
- PRP performance: The dynamic method produces better average solutions than the static method for all instance sets except 200-B and 200-C.Its broader speed exploration helps smaller instances, whereas tighter time windows and larger instances can make convergence slower.
- Instance difficulty: Higher speed diversity is associated with larger gaps and longer convergence times, indicating greater difficulty when routes require more varied speeds.The analysis links this difficulty to the interaction among speed, distance, and time-window feasibility.
- Other green VRPs: ILS-SP-SOA finds 22 new FCVRP best-known solutions and achieves average gaps of 0.16% and 0.31% on the two FCVRP benchmark sets.For EMVRP, the corresponding average gaps are 0.09% and 0.08%, and service-time and route-duration constraints do not dramatically affect solution cost.
6 Concluding remarks
The paper proposes ILS-SP-SOA, a matheuristic that jointly optimizes routes and speeds for PRP, FCVRP, and EMVRP, achieving consistently high-quality solutions and outperforming prior methods. It also identifies tighter integration of speed decisions within local search as an important direction for further work.
- ILS-SP-SOA combines Iterated Local Search, Set Partitioning, and Speed Optimization to solve PRP, FCVRP, and EMVRP.
- Extensive computational experiments found high-quality, consistent solutions that outperform previous methods from the literature.
- Two new PRP instance sets are more challenging, especially when feasible solutions require speeds differing from the optimal speed.Choosing appropriate non-optimal speeds can make good or feasible routing solutions difficult to obtain.
- Further research should embed speed decisions more tightly within local search through larger combined neighborhoods and efficient move evaluation.The authors caution that exploring such neighborhoods may be highly time-consuming.
A Fuel consumption model
The PRP fuel-consumption model is based on a comprehensive emissions model and uses constants representing fuel properties, vehicle characteristics, and road conditions. Under zero acceleration and road inclination, it can be rewritten using four aggregated coefficients.
- The PRP fuel-consumption model is based on a comprehensive emissions model from prior emissions research.
- The model parameters capture fuel properties, vehicle characteristics, and road conditions including acceleration and road inclination.The road-related term is α_ij = τ_ij + g sin θ_ij + gC_r cos θ_ij.
- Assuming zero acceleration and road inclination, the fuel-consumption expression can be rewritten in an alternative form.
- The alternative formulation uses four aggregated coefficients defined as w1 = λkN_V, w2 = λwγgC_r, w3 = λγgC_r, and w4 = λβγ.
B Results for the PRP
The computational experiments use discretized vehicle speeds and report results for PRP instances ranging from 10 to 200 customers. The discretization produces very high-quality upper bounds in general.
- 500 speed levels are used in the discretization because considering all possible speed values is impractical.
- The speed-discretization generally leads to very high-quality upper bounds.
- The results are organized for PRP instances with 10, 50, 100, and 200 customers.