Vehicle routing for hazardous material transportation

Abstract

The main objective of this thesis is to study the hazardous materials (HazMat) transportation problem considered as a heterogeneous fleet vehicle routing problem. HazMat transportation decisions comprise different and sometimes conflicting objectives. Two are considered in this work, the total routing cost and the total routing risk. The first task undertaken was the formulation of a mathematical model for the routing risk minimization, which depends on the type of vehicle, the material being transported, and the load change when the vehicle goes from one customer to another. A piecewise linear approximation is employed to keep a mixed integer linear programing formulation. Hybrid solution methods based on neighborhood search are explored for solving the routing risk minimization. This includes the study of neighborhood structures and the development of a Variable Neighborhood Descent (VND) algorithm for local search, and a perturbation mechanism (shaking neighborhoods). A postoptimization procedure is applied to improve the solution quality. Finally, two different solution approaches, a multi-objective dominance-based algorithm and a meta-heuristic ϵ-constraint method are employed for addressing the multi-objective version of the problem. Two performance metrics are used: the hypervolume and the ∆-metric. The front approximations show that a small increment in the total routing cost can produce a high reduction in percentage of the expected consequences given the probability of a HazMat transportation incident.

Résumé: L’objectif de cette thèse est d’étudier le problème du transport de matiêres dan- ` gereuses (HazMat) vu comme un probleme de tournées de véhicules à flotte hétèrogène. Les dècisions pour ce type de transport comportent des objectifs différents, parfois antagonistes. Deux sont pris en compte dans ce travail, le coût et le risque. La première tâche entreprise a été la formulation d’un modèle mathématique pour la minimisation du risque, qui depend du type de véhicule, du matériel transporté et du changement de charge lorsque le véhicule passe d’un client à un autre. Une approximation linéaire par morceaux est utilisée pour conserver une formulation de programmation linéaire en nombres entiers mixtes. Des méthodes hybrides basées sur des explorations de voisinages sont proposées pour traiter la minimisation du risque. Cela comprend l’étude des structures de voisinages et le développement d’un algorithme de descente à voisinages variables (VND) pour la recherche locale, ainsi qu’un mécanisme de perturbation des solutions. Une post-optimisation est appliquée pour améliorer la qualité des solutions obtenues. Enfin, deux approches, un algorithme base sur la dominance multi-objectif et une méta-heuristique de type ϵ- contrainte, sont développes pour traiter la version multi-objectif. Deux mesures de performance sont utilisées : l’hypervolume et la ∆-metrique. Les approximations de fronts montrent qu’une légère augmentation du coût total des tournées peut entraîner une forte réduction en pourcentage des risques.

Resumen: El objetivo principal de esta tesis es estudiar el problema del transporte de materiales peligrosos (HazMat hazardous materials) modelado como un problema de ruteo de vehículos con flota heterogénea (HVRP ´ heterogeneous fleet vehicle routing problem). Las decisiones en el transporte de HazMat comprenden considerar objetivos diferentes y a veces contradictorios. Dos son los objetivos considerados en este trabajo, el costo y el riesgo total de ruteo. La primera tarea realizada fue la formulación de un modelo matemático para la minimización del riesgo de ruteo, que depende del tipo de vehículo, el material que se transporta y el cambio en el tamaño de la carga cuando el vehículo pasa de un cliente a otro. Se emplea una aproximación lineal por partes de la función objetivo para mantener una formulación de programación lineal entera mixta. Se exploran métodos híbridos de solución basados en búsqueda por vecindarios para resolver el problema de minimización del riesgo total de ruteo. Esto incluye el estudio de las estructuras del vecindario y el desarrollo de un algoritmo de descenso de vecindario variable (VND variable neighborhood descent) para realizar la búsqueda local, y de mecanismos de perturbación (estructuras de vecindario para perturbar las soluciones). Se aplica un procedimiento post-optimización (SP set partitioning) para mejorar la calidad de las soluciones. Finalmente, se emplean dos enfoques de solución diferentes para abordar la versión multi-objetivo del problema, un algoritmo basado en la dominancia Pareto y un método ϵ-constraint heurísticos. Se utilizan dos indicadores de rendimiento para algoritmos multiobjetivo: el hypervolumen y la métrica ∆. Las aproximaciones del frente Pareto obtenidas muestran que un pequeño incremento en el costo total de ruteo puede producir una gran reducción en el porcentaje de las consecuencias esperadas dada la probabilidad de un incidente de transporte de materiales peligrosos.