Study On Hazardous Materials Vehicle Routing Problem And Its Algorithms

It is very important to study the safety management of hazardous material because of its inherent dangers. And hazardous materials accidents have the characteristics of low probability and high hazard, and once an accident occurs, the damage may cause huge damage. This paper mainly studies the single-depot and multi-depot hazardous materials vehicle routing problem (HVRP), and also studies the algorithms of solving them.HVRP is NP-hard, and the heuristic algorithms are the main method used for solving it. In this paper we combined the advantages of GA, PSO and L-BFGS to provide a new hybrid algorithm:the genetic-particle swarm optimization algorithm with enhanced local search ability (L-GPS). In addition, the random perturbation strategy and the optimal switching point evaluation (OSE) strategy were implemented to strengthen search efficiency and balance dynamically the local and global search ability, respectively. Numerical experiments show that the algorithm is effective to solve the NP-hard problem, and it lays the foundation for the further research of the algorithm design.The hazardous materials vehicle routing problem can be divided into single-depot problem and multi-depot problem. For single-depot problem, this paper proposes a new bi-objective optimization model considering the risk and cost. The risk measurement of the model considers the change of the loading, which reflects the nature of hazardous material transportation. New decision variables are introduced to describe the access sequence of demand point. Compared with the traditional VRP model, the new model reduces the number of decision variables and constraint conditions, which simplifies the traditional model expression. The model is solved by an improved particle swarm algorithm, and the non-dominated solution method combines with the hybrid strategy of population to deal with bi-objective problems. Local search strategy is added in the iterative process to enhance the efficiency of the algorithm. Numerical experiment shows that the improved algorithm has better search efficiency than the traditional particle swarm algorithm and can solve the new model effectively.For multi-depot problem, it is extended on the basis of the single-depot problem, this paper also proposes a new bi-objective optimization model considering the risk and cost for multi-depot problem, and a two-stage heuristic algorithm is proposed to solve the model. First, a novel classification algorithm was proposed to transfer multi-depot problem to several single-depot problems. Then use the improved particle swarm optimization algorithm to optimize each single-depot problem. Numerical experiments show that the two-stage heuristic algorithm can solve the multi-depot problem model effectively and efficiently.