References of "François, Véronique"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailAdaptive large neighborhood search for multi-trip vehicle routing with time windows
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

in Transportation Science (in press)

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context of city logistics. Heuristic solution methods for multi-trip vehicle routing problems often separate routing and assignment phases in order to create trips and then assign them to the available vehicles. We show that this approach is outperformed by an integrated solution method in the presence of time windows. We use an automatic configuration tool to obtain efficient and contextualized implementations of our solution methods. We provide suitable instances for the MTVRPTW as well as an instance generator. Also, we discuss the relevance of two objective functions: the total duration and the total travel time. When minimizing the travel time, large increases of waiting time are incurred, which is not realistic in practice. [less ▲]

Detailed reference viewed: 28 (6 ULiège)
See detailLarge neighborhood search approaches for multi-trip vehicle routing with time windows and driver shifts
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

Conference (2018, July)

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW) and we assume that the working time of each vehicle may not exceed a maximum duration smaller than the planning horizon. We ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW) and we assume that the working time of each vehicle may not exceed a maximum duration smaller than the planning horizon. We seek to minimize the total working time, implying that vehicle start times are explicit decision variables. We develop two adaptive large neighborhood search approaches based on different solution representations. The first method treats each vehicle journey as a giant tour that includes trip delimiters. The second one works on separate trips before assigning them to the available vehicles and scheduling them. We configure both methods using an automatic algorithm configuration package and show that the first one is more efficient in the presence of time windows, especially when these are tight. We obtain high quality results on MTVRPTW benchmark instances. We propose a generator to produce instances which characteristics naturally favor the creation of multi-trips. We also show that minimizing the total working time of the vehicles instead of the total distance is suitable in the presence of time windows since accepting a small deterioration in terms of traveled distance has a large positive impact on the working time. This effect increases as the size of time windows decreases. [less ▲]

Detailed reference viewed: 20 (4 ULiège)
Full Text
See detailNeighborhood Search Algorithms for Multi-Trip Vehicle Routing
François, Véronique ULiege

Doctoral thesis (2018)

Think about the lines of trucks we overtake on highways. Each of these trucks is performing a journey that may include several delivery or pickup operations before getting to a depot. And each of these ... [more ▼]

Think about the lines of trucks we overtake on highways. Each of these trucks is performing a journey that may include several delivery or pickup operations before getting to a depot. And each of these journeys is generally determined through a large-scale planning process that concerns a fleet of vehicles. While establishing such a plan, transport operators organize vehicle journeys with an underlying objective such as the minimization of the transportation cost or the maximization of the service level. During the planning process, at least the following decisions have to be made: which customers are going to be visited by each vehicle and in which order. This is a difficult problem to solve even for as few as several tens of customers. In the literature, it is referred to as the vehicle routing problem, which has been extensively studied for nearly six decades. When solving a vehicle routing problem in a practical context, industry or company-specific constraints have to be taken into account, constantly providing the scientific community with new challenges. One of these calls for deciding how many times and when each vehicle should come back to a depot for loading purposes, besides determining the attribution of customers to vehicles and the related visit sequences. The underlying problem is called the multi-trip vehicle routing problem since each vehicle may perform more than one trip during the planning period, trips being separated by loading operations. Such problems are especially relevant in the field of city logistics. In this thesis, we propose a tailored heuristic approach to solve the multi-trip routing problem and compare it to a more classical solution scheme. We extend both solution methods and compare them on a variant of the problem that takes into account time windows and driver shifts. We configure our methods using an automatic algorithm configuration software and obtain numerical results that show that our tailored approach is very effective, especially in the presence of time windows. Moreover, we provide insights about the behavior of several algorithmic components. Also, we question algorithmic development methodologies and benchmark instances commonly used, and we propose related methodological contributions. [less ▲]

Detailed reference viewed: 63 (16 ULiège)
See detailHome chemotherapy: Integrating the production and administration of drugs
Arda, Yasemin ULiege; Cattaruzza, Diego; François, Véronique ULiege et al

Conference (2018, February)

We introduce an integrated production scheduling and vehicle routing problem originally motivated by the rising trend of home chemotherapy. Oncology departments of Belgian hospitals have a limited ... [more ▼]

We introduce an integrated production scheduling and vehicle routing problem originally motivated by the rising trend of home chemotherapy. Oncology departments of Belgian hospitals have a limited capacity to administer chemotherapy treatments on site. Also, patients in a stable condition often prefer to get their treatment at home to minimize its impact on their personal and professional life. The optimization of underlying logistical processes is complex. At the operational level, chemotherapy drugs must be produced in the hospital pharmacy and then administered to patients at home by qualified nurses before the drugs expire. The lifetime of the drug, i.e., the maximum period of time from the production start until the administration completion, is sometimes very short, depending on the treatment type. The problem we consider calls for the determination, for each patient, of the drug production start time and administration start time, as well as the assignment of these two tasks to a pharmacist and a nurse respectively. Drugs may be produced by any of the available pharmacists which are considered to be homogeneous. The working duration of a pharmacist is the time elapsed between the production start time of the first drug and the completion time of the last drug. The allowed working duration of each pharmacist is limited but the start time of each working shift is a decision variable implicitly defined by the production schedule. Drugs are administered by nurses that have a limited working duration. The administration of each drug must be scheduled within a time window that depends on the concerned patient and before the drug expires. This expiry aspect is crucial since it calls for the integration of the scheduling and the routing aspects of the problem. Multiple trips are allowed, i.e., each nurse may come back at the hospital during its journey to take drugs recently produced. The objective of the problem is to minimize the total working time of pharmacists and nurses. We address this problem heuristically using destroy-and-repair mechanisms and allowing infeasible solutions to be visited. The main challenge is that a small change in the production schedule or the administration schedule affects other decision variables in a cyclic fashion. Thus, the change in the objective function associated to a given move is difficult to evaluate efficiently. To circumvent this issue, we propose to iterate between the production and the routing subproblems, by imposing constraints on one of the subproblems depending on the incumbent solution of the other. Moves on the solution of one subproblem are thus evaluated seemingly independently from the other one. Then, occasionally, an exact procedure is called to determine the optimum schedule of the integrated incumbent solution given the task sequence of each pharmacist and of each nurse. [less ▲]

Detailed reference viewed: 25 (3 ULiège)
See detailNeighborhood search approaches for a multi-trip vehicle routing problem with time windows
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

Conference (2017, July 10)

We consider a multi-trip vehicle routing problem with time windows where each vehicle can perform several routes to serve the customers. Besides imposing a time window at the depot, we also assume that ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows where each vehicle can perform several routes to serve the customers. Besides imposing a time window at the depot, we also assume that the working time of each vehicle may not exceed a maximum duration. The pursued objective is the minimization of the total working time. In this context, starting early to ensure the satisfaction of time window constraints has a negative impact on the objective function and on the maximum allowed working time constraint. Thus, vehicle start times are explicit decision variables. We compare two large neighborhood search approaches. The first one combines vehicle routing heuristics with bin packing techniques aimed at assigning routes to vehicles. The second one makes use of specific multi-trip operators designed to tackle simultaneously the routing and the assignment aspects of the problem. We show that the proposed multi-trip operators are more suitable for constrained instances with tight time windows. An automatic configuration tool is used to find high quality results. Moreover, it allows us to gain knowledge about the behavior of algorithmic components. We also question the impact of commonly employed heuristic components. [less ▲]

Detailed reference viewed: 22 (3 ULiège)
Full Text
See detailAdaptive large neighborhood search for multi-trip vehicle routing with time windows
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

E-print/Working paper (2017)

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context ... [more ▼]

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW), in which each vehicle can perform several trips during its working shift. This problem is especially relevant in the context of city logistics. Heuristic solution methods for multi-trip vehicle routing problems often separate routing and assignment phases in order to create trips and then assign them to the available vehicles. We show that this approach is outperformed by an integrated solution method in the presence of time windows. We use an automatic configuration tool to obtain efficient and contextualized implementations of our solution methods. We provide suitable instances for the MTVRPTW as well as an instance generator. Also, we discuss the relevance of two objective functions: the total duration and the total travel time. When minimizing the travel time, large increases of waiting time are incurred, which is not realistic in practice. [less ▲]

Detailed reference viewed: 63 (24 ULiège)
Full Text
See detailInstances for the Multi-Trip Vehicle Routing Problem with Time Windows
François, Véronique ULiege; Arda, Yasemin ULiege

Software (2017)

Instance generator and instance files for the Multi-Trip Vehicle Routing Problem with Time Windows: the folder contains an instance generator usable in a web browser (no installation required), instance ... [more ▼]

Instance generator and instance files for the Multi-Trip Vehicle Routing Problem with Time Windows: the folder contains an instance generator usable in a web browser (no installation required), instance files (.txt) and a description of the problem and instance creation process (.pdf). [less ▲]

Detailed reference viewed: 48 (6 ULiège)
Full Text
Peer Reviewed
See detailLarge neighborhood search for multi-trip vehicle routing
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege et al

in European Journal of Operational Research (2016), 255(2), 422-441

We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close ... [more ▼]

We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances. [less ▲]

Detailed reference viewed: 113 (34 ULiège)
See detailNeighborhood search approaches for multi-trip vehicle routing problems
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege

Conference (2016, July 06)

We introduce two large neighborhood search approaches for solving the multi-trip vehicle routing problem (MTVRP), where each vehicle can perform several routes to serve a set of customers. The problem ... [more ▼]

We introduce two large neighborhood search approaches for solving the multi-trip vehicle routing problem (MTVRP), where each vehicle can perform several routes to serve a set of customers. The problem specifically arises when travel times between customers are short and/or when demands are large. It has been commonly solved in the literature by mixing vehicle routing heuristics and bin packing techniques aimed at assigning routes to vehicles. As an alternative, we propose specific operators that tackle the routing and the assignment aspects of the problem simultaneously. The introduced methods are compared both for the MTVRP and the version with time windows, in which the assignment part of the problem becomes more challenging. In the latter, besides considering a time window at the depot, the working time of each vehicle may not exceed a maximum duration, while its start time is a decision variable. Beyond providing several best known solutions for benchmark instances of the MTVRP, we focus on understanding the behavior of the algorithms. An automatic configuration tool is used, not only to improve the quality of the results, but also as a mean to gain knowledge about algorithm design options and their interactions. We question the impact of several heuristic components and in particular those of the roulette wheel mechanism and of the adaptive memory of routes. [less ▲]

Detailed reference viewed: 44 (7 ULiège)
Full Text
See detailLarge neighborhood search for multi-trip vehicle routing
François, Véronique ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege et al

E-print/Working paper (2015)

We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The ... [more ▼]

We consider two large neighborhood search approaches for the multi-trip vehicle routing problem, where each vehicle can perform several routes during the working shift to serve a set of customers. The problem specifically arises when customers are close to each other and/or when the demands are large. A common approach in the literature consists in solving this problem by mixing vehicle routing heuristics with bin packing routines to assign routes to vehicles. We compare this approach with the use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. We provide several best known solutions for benchmark instances. At the end of the work, we give insights about the proposed algorithm configurations by analyzing the behavior of several method components. [less ▲]

Detailed reference viewed: 151 (19 ULiège)
Peer Reviewed
See detailSpecific Multi-trip Operators for Vehicle Routing Problems
Arda, Yasemin ULiege; Crama, Yves ULiege; François, Véronique ULiege et al

Conference (2014, July 17)

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem use existing VRP ... [more ▼]

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem use existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. In this work, specific local search operators for the VRPM are proposed. Heuristics using these operators are compared with classical solution techniques mentioned above. [less ▲]

Detailed reference viewed: 67 (5 ULiège)
See detailVehicle routing problems with multiple trips: using specific local search operators
Arda, Yasemin ULiege; Crama, Yves ULiege; François, Véronique ULiege et al

Conference (2014, June 25)

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing ... [more ▼]

In vehicle routing problems with multiple trips (VRPM), each vehicle is allowed to perform more than one trip during its working period. Classical solution techniques for this problem make use of existing VRP heuristics to create trips, together with bin packing methods aimed at assigning these trips to the available vehicles. The first contribution of this work is to propose specific local search operators for the VRPM. The operators directly integrate the multi-trip structure of the problem within well-known VRP operators. As a second contribution, heuristics using these operators are compared with classical solution techniques mentioned above. The comparison is performed by using the adaptive large neighborhood search metaheuristic as a common basis for both methods. The most classical version of the problem is studied as well as a variant involving time windows [less ▲]

Detailed reference viewed: 137 (10 ULiège)
Full Text
See detailAn adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts
Arda, Yasemin ULiege; Crama, Yves ULiege; François, Véronique ULiege

Conference (2013, February 13)

This study analyzes a rich vehicle routing problem with multiple trips and driver shifts. The considered problem features are inspired from the practical case of a Belgian distribution company. Along with ... [more ▼]

This study analyzes a rich vehicle routing problem with multiple trips and driver shifts. The considered problem features are inspired from the practical case of a Belgian distribution company. Along with the multi-trip component, characteristics of this particular problem include time windows, pickup and delivery customers, and site-vehicle dependencies. Internal and external fleets are considered with different cost structures and driver shifts constraints. An adpative large neighborhood search is used to treat the problem. [less ▲]

Detailed reference viewed: 219 (8 ULiège)
Full Text
See detailVariable Neighborhood Search applied to the Vehicle Routing Problem
François, Véronique ULiege

Learning material (2011)

Detailed reference viewed: 92 (19 ULiège)
Full Text
See detailAimms - Tutoriel en une heure à l’usage des débutants
Bay, Maud ULiege; François, Véronique ULiege

Learning material (2009)

Detailed reference viewed: 349 (21 ULiège)