A Hybrid Algorithm For The Multi-objective Time Dependent Vehicle Routing Problem In Shanghai Jiao Tong University

This paper presents a real road network case based on the timedependent vehicle routing problem with time windows (TDVRPTW),which involves optimally routing a fleet of vehicles with fixed maxcapacity that services a set of customers with known demands when trafficconditions are time dependent and services at customers are only availablein their own time tables. Considering the time-dependent traffic conditionsand customers’ available service times, we combine total travel length andtotal travel time together with coefficients to express the total travel cost.A hybrid algorithm based on the Genetic Algorithm (GA) and theMulti Ant Colony System (MACS) is introduced in order to find optimalsolutions that minimize two hierarchical objectives: the number of vehiclesneeded and the total travel cost.The test results of the hybrid algorithm were compared with onesobtained by the GA and the MACS and show that the integrated algorithmoutperforms both of its traditional ones in terms of the convergence speedtowards optimal solutions. The hybrid algorithm takes advantage of thefast iterative feature of the MACS and maintains the ability of the GA insearching global optimal solutions. In conclusion, the hybrid algorithm canfind solutions minimized in both objectives faster and provide betterperformance in a real TDVRPTW problem.