For the realistic vehicle routing plan, this research attempts to formulate a mathematical model for the Time-Dependent Vehicle Routing Problem (TDVRP) and propose a Genetic Algorithm (GA) to solve the problem. The formulation of the problem considers multiple vehicles with different capacities, pick-up or delivery demands with soft time-windows, real-time service requests, and real-time variations in travel times between demand nodes. The objective in this paper is to minimize the total cost that consists of the fixed cost for used vehicles, the customer inconvenience costs that result from breaking time windows, and the routing cost. The research presents a mixed integer linear programming formulation of the TDVRP.; This research present the test results of the parameters used in the GA, including the number of multiple runs, the size of the population, the stopping criteria, the crossover rate and the mutation rate. We also perform sensitivity analysis with respect to changes in the model parameters. These parameters include the fixed cost, the waiting cost, the delay cost, the routing cost, and the vehicle capacity.; We test the proposed GA on some test problems and compare the GA results with the exact solutions for small test problems. We also compare the GA results with the Lower Bounds (L.B) that are obtained for the solution of the larger size problems.; Finally, we performed a simulation test on a network. We designed a time dependent shortest path algorithm to calculate the travel time between the demand nodes on the network. In the simulation test, we compared two results, one was from the time-dependent routing plan and other was from the deterministic routing plan. The simulation tests showed that the time dependent routing plan could save cost, as the uncertainty in travel time forecasting increases. Also more open rerouting plan can save cost, as the uncertainty in the travel time forecasting increases.
展开▼
