Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Recherche à voisinage large pour le problème de tournées de véhicules à voyages multiples François, Véronique ; Arda, Yasemin ; Crama, Yves et al Conference (2016, February 10) Detailed reference viewed: 24 (1 ULg)Combining acceleration techniques for pricing in a VRP with time windows Michelini, Stefano ; Arda, Yasemin ; 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: 21 (2 ULg)Large neighborhood search for multi-trip vehicle routing François, Véronique ; Arda, Yasemin ; Crama, Yves 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: 126 (17 ULg)Branch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time ; Arda, Yasemin ; Crama, Yves 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: 33 (2 ULg)A general lotsizing problem with uncertain product returns Amand, Guillaume ; Arda, Yasemin Conference (2015, July 15) We consider a single-stage system that produces a range of final products. The demands of the final products are supposed deterministic over a finite planning horizon. Each unit of demand has to be ... [more ▼] We consider a single-stage system that produces a range of final products. The demands of the final products are supposed deterministic over a finite planning horizon. Each unit of demand has to be fulfilled at the period that it appears using either the production of that period or the inventory carried over from the earlier periods. The final products can either be manufactured using purchased materials or remanufactured using remanufacturable returned products. For each final product, the manufactured and remanufactured items are perfectly substitutable. The returned products are collected at the start of each period but the quantities obtained are unknown until the collection. The return inventories accumulate as remanufacturable returned items are received. The manufacturing and remanufacturing processes of all the final products are executed on a same machine. In each time period, multiple products can be processed but the total production quantity is limited by the time availability of the machine during this period. Whenever production is switched from one final product to another, a sequence dependent setup cost is incurred and a sequence depen- dent setup time is consumed from the available time capacity. Different stochastic combinatorial optimization methods as well as dynamic programming methods are proposed, tested and compared. [less ▲] Detailed reference viewed: 42 (9 ULg)Exact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time Michelini, Stefano ; Arda, Yasemin ; Crama, Yves et al Conference (2015, June 10) We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first ... [more ▼] We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch- and-Price (BP) algorithm considering the related pricing subproblem, an elementary shortest path problem with resource constraints (ESP- PRC). We discuss past, present and planned research on this exact so- lution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲] Detailed reference viewed: 24 (5 ULg)Exact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time Michelini, Stefano ; Arda, Yasemin ; Crama, Yves et al Conference (2015, February 05) We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a ... [more ▼] We consider a VRP with time windows in which the total cost of a solution depends on the duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch-and-Price algorithm considering the pricing subproblem, an elementary shortest path problem with resource constraints (ESPPRC). We discuss research on this exact solution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic. [less ▲] Detailed reference viewed: 74 (22 ULg)Multi-period vehicle loading with stochastic release dates Arda, Yasemin ; Crama, Yves ; Kronus, David et al in EURO Journal on Transportation and Logistics (2014), 3(2), 93-119 This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be ... [more ▼] This paper investigates a multi-period vehicle loading problem with stochastic information regarding the release dates of items to be transported. The deterministic version of the problem can be formulated as a large-scale set covering problem. Several heuristic algorithms are proposed to generate decision policies for the stochastic optimization model over a long rolling horizon. The resulting policies have been extensively tested on instances which display the main characteristics of the industrial case-study that motivated the research. The tests demonstrate the benefits of the multi-period stochastic model over simple myopic strategies. A simple and efficient heuristic is shown to deliver good policies and to be robust against errors in the estimation of the probability distribution of the release dates. [less ▲] Detailed reference viewed: 206 (53 ULg)Specific Multi-trip Operators for Vehicle Routing Problems Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 50 (4 ULg)A General Lotsizing and Scheduling Problem with Stochastic Product Returns Amand, Guillaume ; Arda, Yasemin Conference (2014, July 15) We consider a multi-product capacitated lotsizing and scheduling problem with sequence-dependent setups and stochastic product returns. The returned products accumulate in an input inventory and can be ... [more ▼] We consider a multi-product capacitated lotsizing and scheduling problem with sequence-dependent setups and stochastic product returns. The returned products accumulate in an input inventory and can be sold as new items after a remanufacturing process. The deterministic demand of end items can also be satisfied through a manufacturing process that is fed by an unlimited source of raw materials. An approximate dynamic algorithm is developed to solve both single-item and multi-items cases. [less ▲] Detailed reference viewed: 31 (6 ULg)Optimization of the service start time for an elementary shortest path problem with time windows Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande E-print/Working paper (2014) We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their ... [more ▼] We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their individual time windows. When the vehicle visits a customer, it delivers the customer's demand and collects a revenue in return for the delivery. The vehicle can start its trip at any desired time. The transportation cost is a function of both the total distance traveled and the duration of the assigned trip. The objective is to determine the service start time from the depot, the subset of customers to be served, and the trip to be performed so as to minimize the total loss, which is calculated as the di erence between the transportation cost and the revenue collected from the customers. We develop two exact dynamic programming algorithms which can deal with an in nite number of Pareto-optimal states arising from the fact that the starting time and the duration of the trip act like continuous decision variables. We report computational results obtained with these algorithms and with a faster heuristic for the elementary shortest path problem. We also examine the performance of these algorithms when they are used to solve the pricing subproblem arising in the framework of a column generation algorithm for a related vehicle routing problem with time windows. [less ▲] Detailed reference viewed: 237 (13 ULg)Vehicle routing problems with multiple trips: using specific local search operators Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 111 (10 ULg)Service Start Time Optimization in Elementary Shortest Path Problems with Resource Constraints Arda, Yasemin ; ; Crama, Yves Scientific conference (2014, June 12) Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and ... [more ▼] Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and branch-and-price. We consider an elementary shortest path problem with resource constraints, where there is a capacitated single vehicle at the depot for serving a set of customers by respecting their associated time windows. The vehicle can start serving the customers at any desired time and can be used for a fixed amount of time. The total transportation cost is defined as a function of the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. Every time the vehicle visits a customer, it delivers the required load and collects a revenue in return for the delivery. The objective is to determine the trip to be performed and the service start time from the depot so as to minimize the total loss, which is calculated as the total transportation cost minus the collected revenues. In this study, we develop two exact dynamic programming algorithms which can deal with an infinite number of Pareto-optimal states arising from the fact that the vehicle can depart from the depot at any point in time and charges depending on the amount of time it spends for serving customers. Apart from reporting computational results for our elementary shortest path problem, we also embed it into a column generation framework for the corresponding capacitated vehicle routing problem with time windows. Recent results for the developed branch-and-price algorithm are also reported. [less ▲] Detailed reference viewed: 21 (0 ULg)An exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start time Arda, Yasemin ; Crama, Yves ; Kucukaydin, Hande Conference (2014, January 31) We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start ... [more ▼] We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start servicing the customers at any desired time, but it can be used for a fixed amount of time. The total transportation cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. On the other hand, each served customer yields a revenue. Thus, the aim is to identify the path to be followed and the start time of the vehicle from the depot that minimize the total transportation cost minus the gained revenues. This kind of a problem can be encountered as a pricing subproblem when a branch-and-price algorithm is applied to solve vehicle routing problems with additional constraints. In such a case, the revenues correspond to the dual prices of the visited vertices. It is known that the classical ESPPRC can be solved to optimality by implementing a dynamic programming (DP) algorithm. However, our problem has to take an infinite number of Pareto-optimal states into consideration, since the vehicle can leave the depot at any point in time and charges depending on the total traveling and waiting time. We propose an exact DP algorithm which can deal with an infinite number of Pareto-optimal states by representing total traveling and waiting time as a piecewise linear function of the service start time at the depot and develop suitable dominance rules. Furthermore, a column generation algorithm is devised for solving the relaxed set covering formulation of the related vehicle routing problem where new columns are determined by the proposed DP algorithm. Finally, computational results are presented. [less ▲] Detailed reference viewed: 143 (1 ULg)Optimization of Service Start Time for an Elementary Shortest Path Problem Kucukaydin, Hande ; Arda, Yasemin ; Crama, Yves Conference (2013, July 08) We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers ... [more ▼] We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers with a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where the delivery and backhaul customers are considered to be two disjoint sets. Split deliveries and pick-ups are not allowed. In this problem, the vehicle may be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. Namely, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the objective is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the total of the distance and time costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices. In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, computational results are presented. [less ▲] Detailed reference viewed: 92 (14 ULg)Neighborhood Search Approaches for a Vehicle Routing Problem with Multiple Trips and Driver Shifts Arda, Yasemin ; Crama, Yves ; François, Véronique Conference (2013, July 08) Detailed reference viewed: 49 (16 ULg)A two-stage stochastic programming model for a comprehensive disaster management problem Döyen, Alper ; Arda, Yasemin Conference (2013, July 03) A periodic disaster preparedness model that incorporates mitigation, response, and recovery related decisions is proposed. The objective is to minimize the total cost of relief item transportation and ... [more ▼] A periodic disaster preparedness model that incorporates mitigation, response, and recovery related decisions is proposed. The objective is to minimize the total cost of relief item transportation and shortage as well as recovery costs of buildings and links under a limited retrofitting budget. The problem is formulated as a two-stage stochastic programming model. While retrofitting decisions are the binary first-stage variables, relief flows and shortage amounts constitute continuous second-stage variables. An efficient solution approach that employs the integer L-shaped method is proposed. [less ▲] Detailed reference viewed: 45 (4 ULg)General lotsizing in a closed-loop supply chain with uncertain returns Amand, Guillaume ; Arda, Yasemin Conference (2013, July 03) We consider a multi-product capacitated lotsizing and scheduling prob- lem with sequence-dependent setups and stochastic product returns. The returned products accumulate in an input inventory and can be ... [more ▼] We consider a multi-product capacitated lotsizing and scheduling prob- lem with sequence-dependent setups and stochastic product returns. The returned products accumulate in an input inventory and can be sold as new items after a remanufacturing process. The determinis- tic demand of end items can also be satisfied through a manufacturing process that is fed by an unlimited source of raw materials. An ap- proximate dynamic algorithm is developed to solve both single-item and multi-items cases. [less ▲] Detailed reference viewed: 42 (5 ULg)An elementary shortest path problem with variable service start time Kucukaydin, Hande ; Arda, Yasemin ; Crama, Yves Conference (2013, May 02) We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On ... [more ▼] We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where a customer is either a delivery or a backhaul customer, but not both. Split deliveries and pick-ups are not allowed. In this problem, multiple trips are allowed so that the vehicle can be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. In other words, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the aim is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the routing costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices. In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, we present computational results. [less ▲] Detailed reference viewed: 58 (1 ULg)An adaptive large neighborhood search for a vehicle routing problem with multiple trips and driver shifts Arda, Yasemin ; Crama, Yves ; François, Véronique 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: 202 (8 ULg) |
||