Sustainability in vehicle routing and scheduling problems

The first part of the talk presents the Time-Dependent Pollution-Routing Problem (TDPRP), a vehicle routing problem where CO2e emissions and traffic congestion are accounted for.  The presence of traffic congestion during the first period of the day   limits the vehicles speed and increases the amount of vehicle emissions per kilometer. The objective is to determine the assignment and the scheduling of customers to vehicles, the travel speed on each arc of the route and the departure time from each node, so as to minimize a total cost function encompassing labour cost and emissions cost.  We describe an integer linear programming formulation of the TDPRP and we provide an analytical characterization of the optimal solution for a single-arc version of the problem. The theoretical results show that in some cases it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions.

The second part of the talk presents the Departure Time and Speed Optimization Problem (DSOP), a vehicle scheduling problem where CO2e emissions are accounted for. The objective is to determine the departure times and the travel speed of a vehicle traveling on a fixed route, so as to minimize a total cost function composed of labour cost and emissions cost.  We formulate the problem as a dynamic programming problem, and we study the structure and the properties of the value function.  Based on the theoretical results, we derive an efficient solution method, which simplifies into a shortest path problem.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.