This is the second of a two-part seminar session.
Abstract: The pollution routing problem (PRP) is a recent extension of the vehicle routing and scheduling problem (VRSP) that takes environmental objectives into consideration by using fuel consumption as a proxy for CO2 emissions. Fuel consumption in turn is dependent on many different factors including vehicle and congestion characteristics. In this study, regarding the fact that different paths between any pair of required nodes in an urban road network can become optimal for different combinations of departure times, vehicle load, and the vehicle type traversing the path, we formulate and solve a variant of the PRP directly on the original road network, and call it the Steiner Pollution Routing Problem (SPRP). The SPRP accounts for both business and environmental objectives and hence is a multi-objective fleet size and mix time-load-and-vehicle-dependent pollution routing problem with multiple trips and flexible departure times. Solving the SPRP is a demanding task and a multi-phase solution approach has been proposed for the problem. In the first phase a proposed exact network reduction technique is applied to reduce the network size to a considerable extent. Then, in order to approximate the true efficient frontier of the tri-objective instances of the SPRP on the reduced network, a new solution methodology is proposed by hybridizing three main successful concepts: (1) mathematical programming techniques (MTP) for generating the full non-dominated set of integer programming (IP) problems, (2) local search within metaheuristics as single-objective solvers, and (3) multi-objective evolutionary algorithms. In the context of the utilized MTP two IPs are solved in each iteration in search of one as-of-yet unknown non-dominated point, and this task is assigned to a new tailored deterministic geo-temporal route construction and improvement heuristic, a simulated annealing with an exhaustive neighborhood search, and an order-first-split-second memetic algorithm. In the final stage of the algorithm the approximated Pareto front is submitted to an NSGA-II for any further possible improvements. The MILP formulation of the SPRP, the proposed solution algorithm, and some computational results will be discussed in this presentation.