University of California Transportation Center

This research studies a new class of dynamic problem MTVRP where n vehicles are routed in real time in a fast varying environment to pickup and deliver m passengers when both n and m are big. The problem is very relevant to future transportation options involving large scale real-time routing of shared-ride fleet transit vehicles. Traditionally, dynamic routing solutions were found as static approximations for smaller-scale problems or using local heuristics for the larger-scale ones. Generally heuristics used for these types of problems do not consider global optimality. A hierarchical method to solve the MTVRP in three different stages has been developed. Within the optimization process, a particular case of Network Design Problem (NDP) is solved. This paper introduces MTVRP and presents a scheme to solve it. Then, it describes the associated Mass Transport Network Design Problem (MTNDP) and solves the problem. The computational complexities as well as the results are compared.