Scheduling and routing of vehicles for a transportation company

by 1975- Labiad, Noureddine

Labiad, Noureddine: Scheduling and routing of vehicles for a Transportation company. (Under the direction of Professor Russell E King) This work addresses the problem of finding the minimum number of vehicles required to service weekly a set of customers subject to time windows. The specific structure of the problem requires that a full loaded vehicle serve only one customer each time it leaves the depot. As a consequence, all feasible schedules involve the same total distance traveled. The fleet is homogeneous and is located in a common depot. Vehicle capacity is finite, weekly mileage is limited, and split service is not permitted. Four heuristics are developed to obtain feasible solutions. Results are reported for 1000 randomly generated problems with up to 150 deliveries. It is shown that the new heuristics outperform the actual algorithm used by the Transportation Company in terms of computation time and the quality of solution. To gauge the quality of the solutions, three lower bounding procedures are developed. The first considers the ‘bin packing aspect of the problem’ with regard to the maximum weekly mileage. The second exploits the time windows constraints while the third lower bounding method uses a network flow formulation. Biography Noureddine Labiad was born on August 3rd, 1975 in Casablanca, Morocco. He completed his undergraduate degree in Electrical Engineering from Ecole Mohammadia des Ingénieurs, Rabat, Morocco. Right after he graduated, he started his career at La Banque Centrale Populaire as a Business Analyst. After a working experience of 18 months, he joined the multinational Corporation Italcementi Group as a Project Engineer. This last experience grew up his interest in Production and Manufacturing Engineering and his will to pursue his graduate studies in this area. In 2001, he joined North Carolina State University to pursue his Masters degree in Industrial Engineering. He worked as a Teaching Assistant and Research Assistant and was elected to the Honor Society of Phi Kappa Phi. During his studies he worked as Industrial Engineering intern with ABB Inc., Raleigh, NC. ii