The multi-objective Steiner pollution-routing problem on congested urban road networks

This paper introduces the Steiner Pollution-Routing Problem (SPRP) as a realistic variant of the PRP that can take into account the real operating conditions of urban freight distribution. The SPRP is a multi-objective, time and load dependent, fleet size and mix PRP, with time windows, flexible departure times, and multi-trips on congested urban road networks, that aims at minimising three objective functions pertaining to (i) vehicle hiring cost, (ii) total amount of fuel consumed, and (iii) total makespan (duration) of the routes. The paper focuses on a key complication arising from emissions minimisation in a time and load dependent setting, corresponding to the identification of the full set of the eligible road-paths between consecutive truck visits a priori, and to tackle the issue proposes new combinatorial results leading to the development of an exact Path Elimination Procedure (PEP). A PEP-based Mixed Integer Programming model is further developed for the SPRP and embedded within an efficient mathematical programming technique to generate the full set of the non-dominated points on the Pareto frontier of the SPRP. The proposed model considers truck instantaneous Acceleration/Deceleration (A/D) rates in the fuel consumption estimation, and to address the possible lack of such data at the planning stage, a new model for the construction of reliable synthetic spatiotemporal driving cycles from available macroscopic traffic speed data is introduced. Several analyses are conducted to: (i) demonstrate the added value of the proposed approach, (ii) exhibit the trade-off between the business and environmental objectives on the Pareto front of the SPRP, (iii) show the benefits of using multiple trips, and (iv) verify the reliability of the proposed model for the generation of driving cycles. A real road network based on the Chicago's arterial streets is also used for further experimentation with the proposed PEP algorithm.