A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution

Planning hazardous materials distribution routes for servicing a given set of orders within specified time windows is a problem frequently surfacing in a city logistics environment which is characterized by dynamic travel times. The hazardous materials distribution problem involves the determination of the sequence of deliveries and the corresponding paths assigned to each truck. This paper presents the formulation of the hazardous materials distribution problem as a bi-objective time-dependent vehicle routing problem with time windows. The paper presents the mathematical formulation of the problem as an integer network flow model with multiple objectives. The weighted-sum method is applied decomposing the bi-objective vehicle routing and scheduling problem to a series of single-objective instances of the problem, where the objective function is expressed by the weighted sum of the criteria under consideration. A route-building heuristic algorithm is presented for addressing each of the constituent single-objective problems, where stops are inserted iteratively in the front part of the unfinished route. A label-setting algorithm is integrated in the heuristic algorithm for solving the time-dependent shortest path problem with multiple intermediate stops arising after the insertion of any stop in the route. The proposed solution approach has been applied to a set of solvable test problems to assess the accuracy of the heuristic solutions. The results indicate a tolerable deviation of the heuristic solutions from the actual non-dominated solutions. In addition, the proposed algorithm was applied to a set of test problems resembling real-life problem cases. The average computational time needed for solving this type of test problems is not prohibitive.