Skip to Main content Skip to Navigation

Résolution par des algorithmes exacts et approchés de problèmes intégrés d’ordonnancement de la production et de tournées de véhicules

Abstract : We consider in this thesis a set of integrated routing and scheduling problems. A set of orders must be produced and delivered to customers. The production workshop is a permutation flow shop: all the orders are processed in the same order on the machines. We consider inventory costs throughout the entire production process, from the arrival of raw materials until the departure of the final product. Once the orders are completed, they are grouped in batches and delivered to customers by a homogeneous fleet of vehicles. All customers and production locations are different. The delivery cost is composed of a fixed cost per vehicle used and the total traveling costs. Finally, each customer waits for his order at a specific delivery date. If the delivery is late, the agents pay penalty costs. We consider two kinds of agents: the manufacturer and the third-party logistics (3PL) provider. The 3PL provider delivers the orders to the customers. In this thesis, two versions of the problem are adressed : a first version with one produceur and several customers and a second version with several produceurs and one customer. In the first problem, a manufacturer must produce orders for several customers. Two approaches are proposed. In the first one, the manufacturer dominates the decision-making in the system. The manufacturer is in charge of determining the production scheduling, the number of vehicles and their loads and the departure date of each vehicle. The 3PL provider adjusts its decisions and each agent tries to minimize its own costs. Solving mathematical model is inefficient for large instances, so a genetic algorithm and a GRASP (Greedy randomized adaptive search procedure) are proposed to solve the problem. These two heuristics are tested on randomly generated instances and the results show best performances for the genetic algorithm. In the second approach, both agents are part of the same entity. They take decisions and minimize the whole cost together. Furthermore, we consider the composition of batches is known in advance. A two steps resolution method solves its problem. First, for each batch and each possible departure date, a prepossessing finds the delivery route minimizing the delivery and the penalty costs. A branch and bound procedure and heuristics are developed for this step. The second step reuses these results in order to search a production scheduling minimizing the whole problem cost. Both steps of this method are tested and compared. In the second problem, several manufacturers must produce orders for a single customer. Each vehicle of 3PL provider deliveries visits fisrt the manufacturers then delivers the customer. In this approach, the different agents have already determined the routes of vehicles and timetable. The manufacturers must determine the scheduling on the different location and the assigment of the orders to vehicles. Feasible instances are generated and a genetic algorithm is proposed to solve these instances.
Document type :
Complete list of metadata
Contributor : Hugo Chevroton <>
Submitted on : Monday, January 11, 2021 - 1:31:33 PM
Last modification on : Tuesday, February 2, 2021 - 3:27:40 PM
Long-term archiving on: : Monday, April 12, 2021 - 6:53:45 PM


Files produced by the author(s)


  • HAL Id : tel-03099986, version 1


Chevroton Hugo. Résolution par des algorithmes exacts et approchés de problèmes intégrés d’ordonnancement de la production et de tournées de véhicules. Informatique [cs]. Université de Tours - LIFAT, 2020. Français. ⟨tel-03099986⟩



Record views


Files downloads