Dynamic (Time Dependent) Green Vehicle Routing Problem

Project Abstract

This research summarizes recent studies on two versions of the Vehicle Routing Problem, i.e., the time-dependent vehicle routing problem (TD-VRP) and the green vehicle routing problem (G-VRP), for which a time-dependent version is also developed. A new formulation of TD-VRP is proposed that can deal with the time-dependent vehicle routing problem with dynamic demand information and provide the minimum cost routing plan. We also introduce a special case of G-VRP with a mixed fleet of heterogeneous electric and internal combustion engine commercial vehicles. Two different formulations are proposed to solve two different variants of the problem. A constructive heuristic is defined to generate initial feasible solution to the problem. The initial solution is further improved by deconstructing a large part of it and then, rebuilding it with the constructive heuristic. This algorithm is preferred over the local search algorithms as it provides better solutions due to the diversification effect embedded in it by deconstructing a large part of the solution. The results of the implementation of the proposed modes in a number of test problems and a large case study are also presented.

Click or tap to read the full report or read a one-page fact sheet.

Outputs and Outcomes

The proposed formulation for both G-VRP and Time-Dependent G-VRP can handle tradeoffs between the limitation on both types of vehicle, as well as variations in travel time during different periods of operation.
• The proposed heuristic method performs well and provides fairly good results for the generated test problems in terms of solution accuracy and run time, when compared with the exact solution for small problems.
• The result of the sensitivity analysis performed on the solution of heuristic with respect to parameters of LEZ coverage, LEZ penalty cost, emission cap and carbon price, and the customer demand shows the effectiveness of the heuristic algorithm in considering the tradeoffs between ICCVs and ECVs under different LEZ and cap and trade policies.

Universities and Sponsoring Organizations Involved

University of Maryland

Principal Investigator(s)

Dr. Ali Haghani, Email: haghani@umd.edu

Funding Sources and Amounts

USDOT: $36,000, UMD: $18,000 (Match)

Start Date

June 1, 2017

Completion Date

Feb. 7, 2019

Keywords

Original Title of Research: Dynamic Vehicle Routing with Route Guidance for Urban Pickup and Delivery (Core Project)