References of "Arda, Yasemin"
     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: 25 (6 ULiège)
Full Text
Peer Reviewed
See detailThe value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment
Moons, Stef; Braekers, Kris; Ramaekers, Katrien et al

in International Journal of Production Research (2019)

In B2C e-commerce sales, customers expect a fast and low-cost delivery. To be able to fulfill these customer expectations, both warehouse and distribution operations have to be performed in an efficient ... [more ▼]

In B2C e-commerce sales, customers expect a fast and low-cost delivery. To be able to fulfill these customer expectations, both warehouse and distribution operations have to be performed in an efficient and effective way. Ideally, these two supply chain functions should be considered simultaneously in an integrated problem since they are interrelated. In this paper, a record-to-record travel algorithm is proposed to solve the integrated order picking-vehicle routing problem (I-OP-VRP). Experiments with both small-size and large-size instances are conducted. Furthermore, the integrated approach is compared with an approach in which both problems are solved sequentially. Results show that integration leads to increased service levels, i.e., it allows to shorten the time between placing an order and receiving the goods. On top, the integrated approach leads to costs savings of on average 1.8%. Thus, integration is indispensable for a fast and cost-efficient delivery of goods. [less ▲]

Detailed reference viewed: 21 (0 ULiège)
Full Text
Peer Reviewed
See detailA comparative study of branch-and-price algorithms for vehicle routing with time windows and waiting time costs
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Küçükaydın, Hande

Conference (2018, July 10)

Branch-and-price is a leading methodology for solving routing problems. Several studies have investigated labeling algorithms to solve the related pricing problem, which is usually a variant of the ... [more ▼]

Branch-and-price is a leading methodology for solving routing problems. Several studies have investigated labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Solving this problem efficiently is crucial, since it is a performance bottleneck for the branch-and-price procedure. Such algorithms include methods like decremental state space relaxation, ng-route relaxation, and hybrids of these two. These focus on how to treat efficiently the elementarity constraints, since they tend to make label domination difficult, which translates to more computational resources used. In this study, we investigate the performance of these methods in a branch-and-price framework. The problem under consideration is a variant of the vehicle routing problem with time windows in which waiting times have a linear cost. We first parametrize several algorithmic components. Then, we search for good parameter configurations for each algorithm with irace, a tool for automated parameter tuning that generates and runs a very high number of configurations on a set of tuning instances and uses statistical tests to determine the best performing configuration. Finally, we run all final configurations on the Solomon benchmark instances and analyze the results with statistical tests. Our results show that a class of hybrid algorithms with certain features based on ng-route relaxation outperforms all the others. [less ▲]

Detailed reference viewed: 21 (5 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: 19 (4 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)
Full Text
Peer Reviewed
See detailIntegration of order picking and vehicle routing in a B2C e-commerce context
Moons, Stef; Ramaekers, Katrien; Caris, An et al

in Flexible Services and Manufacturing Journal (2018), 30

E-commerce sales are increasing every year and customers who buy goods on the Internet have high service level expectations. In order to meet these expectations, a company’s logistics operations need to ... [more ▼]

E-commerce sales are increasing every year and customers who buy goods on the Internet have high service level expectations. In order to meet these expectations, a company’s logistics operations need to be performed carefully. Optimizing only internal warehouse processes will often lead to suboptimal solutions. The interrelationship between the order picking process and the delivery process should not be ignored. Therefore, in this study, an order picking problem and a vehicle routing problem with time windows and release dates are solved simultaneously using a single optimization framework. To the best of our knowledge, it is the first time that an order picking problem and a vehicle routing problem are integrated. A mixed integer linear programming formulation for this integrated order picking-vehicle routing problem (OP-VRP) is provided. The integrated OPVRP is solved for small instances and the results are compared to these of an uncoordinated approach. Computational experiments show that integration can lead to cost savings of 14% on average. Furthermore, higher service levels can be offered by allowing customers to request their orders later and still get delivered within the same time windows. [less ▲]

Detailed reference viewed: 99 (23 ULiège)
Full Text
See detailA comparative study of labeling algorithms for vehicle routing problems with time windows and waiting time costs
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Küçükaydın, Hande

E-print/Working paper (2017)

Detailed reference viewed: 58 (19 ULiège)
Full Text
Peer Reviewed
See detailBranch-and-price algorithms for a VRP with time windows and variable departure times
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Küçükaydin, Hande

Conference (2017, July 20)

Detailed reference viewed: 29 (6 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
Peer Reviewed
See detailIntegrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion
Moons, Stef; Ramaekers, Katrien; Caris, An et al

in Computers and Industrial Engineering (2017), 104

Production scheduling and vehicle routing are two well-studied problems in literature. Although these supply chain functions are interrelated, they are often solved sequentially. This uncoordinated ... [more ▼]

Production scheduling and vehicle routing are two well-studied problems in literature. Although these supply chain functions are interrelated, they are often solved sequentially. This uncoordinated approach can lead to suboptimal solutions. In the current competitive business environment, companies are searching for methods to save costs and improve their service level. Integrating production and distribution scheduling operations can be an approach to improve the overall performance. This paper focuses on integrated production-distribution operational level scheduling problems, which explicitly take into account vehicle routing decisions of the delivery process. Existing literature on integrated production scheduling and vehicle routing problems is reviewed and classified. Both the problem characteristics of mathematical models and the accompanying solution approaches are discussed to identify directions for further research. [less ▲]

Detailed reference viewed: 119 (17 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: 47 (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: 109 (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
Peer Reviewed
See detailColumn Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Küçükaydin, Hande

Conference (2016, July 05)

We investigate a solution methodology for a variant of the VRP with time windows. In the examined variant, the departure time of each vehicle from the depot can be determined by the decision-maker, who ... [more ▼]

We investigate a solution methodology for a variant of the VRP with time windows. In the examined variant, the departure time of each vehicle from the depot can be determined by the decision-maker, who aims at minimizing the overall duration of the routes, including waiting times, while respecting the maximum allowed working duration of each vehicle. In order to solve this problem with a branch-and-price methodology, we address the associated pricing problem as an elementary shortest path problem with resource constraints (ESPPRC). We propose an adapted bidirectional dynamic programming algorithm for the studied ESPPRC. The decremental state space relaxation (DSSR) technique is also implemented as an acceleration technique both to obtain ng-routes and elementary routes. Several implementation and integration strategies are considered for the DSSR and ng-route relaxation techniques. The ng-route pricing and the elementary route pricing algorithms are compared inside a column generation procedure. For both column generation procedures, the algorithmic choices are made and the values of the numerical parameters are determined using an automatic algorithm configuration tool, the irace package. Finally, we discuss how these column generation procedures can be included as a component in the development of a matheuristic. [less ▲]

Detailed reference viewed: 70 (12 ULiège)
Full Text
Peer Reviewed
See detailCombining acceleration techniques for pricing in a VRP with time windows
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Küçükaydin, Hande

Conference (2016, January 28)

In this study, we investigate a solution methodology for a variant of the VRP with time windows. The cost of each route depends on its overall duration (including waiting times), while the departure time ... [more ▼]

In this study, we investigate a solution methodology for a variant of the VRP with time windows. The cost of each route depends on its overall duration (including waiting times), while the departure time of a vehicle is a decision variable. Furthermore, each route has a maximum permitted duration. In order to solve this problem with a branch-and-price methodology, we study also the associated pricing problem, an elementary shortest path problem with resource constraints (ESPPRC). Compared to the classical ESPPRC, this variant admits an infinite number of Pareto-optimal states. In order to tackle this, it was shown in [1] that it is possible to represent the total travelling time as a piecewise linear function of the service start time at the depot. Together with this representation, an appropriate label structure and domi- nance rules are proposed and integrated into an exact bidirectional dynamic programming algorithm [2]. It is possible to implement certain acceleration techniques in the dynamic program- ming algorithm used to solve the pricing problem. We focus on two of these techniques: decremental state space relaxation (DSSR), introduced in [3], and ng-route relaxation, in- troduced in [4] and [5]. DSSR aims to enforce gradually the constraints on the elementarity of the path, which adversely affect the number of generated and dominated labels. A set of critical nodes is iteratively populated, and elementarity is enforced only on these critical nodes. When using ng-route relaxation, a neighbourhood is defined for each vertex. Then, the labels are extended such that, thanks to this neighbourhood structure, it is possible to allow only cycles that are relatively expensive and therefore less likely to appear in the optimal solution. In this study, we explore several different strategies used to apply these techniques, for example initialization strategies for the critical vertex set in DSSR, or the size of the neighbourhoods for ng-route relaxation. We also analyze two ways of combining DSSR and ng-route relaxation. The different algorithmic choices are represented as categorical parameters. The categorical parameters, together with the numerical ones, can be tuned with tools for automatic algorithm configuration such as the irace package [6]. We discuss how this column generation procedure can be included as a component in the development of a matheuristic based on the idea in [7], which consists in a collaboration scheme between a branch-and-price algorithm, an exact MIP solver, and a metaheuristic. [less ▲]

Detailed reference viewed: 64 (9 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: 150 (19 ULiège)
Peer Reviewed
See detailBranch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time
Küçükaydın, Hande; Arda, Yasemin ULiege; Crama, Yves ULiege et al

Conference (2015, July 15)

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In ... [more ▼]

We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In order to solve the problem to optimality, a branch-and-price (BP) algorithm is implemented recognizing the pertinent pricing subproblem as an elementary shortest path problem with resource constraints (ESPPRC) which can handle an infinite number of labels and employs effective dominance rules. We present the past, present, and future implementations of the BP procedure based on bounded bi-directional search, decremental state space relaxation, and ng-route relaxation. We further discuss the design of BP-based matheuristics which make use of metaheuristics in pricing subproblem resolution, upper bound improvement, and column generation. [less ▲]

Detailed reference viewed: 95 (6 ULiège)