References of "Michelini, Stefano"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailA comparative study of labeling algorithms within the branch-and-price framework for vehicle routing with time windows
Michelini, Stefano ULiege

in 4OR: A Quarterly Journal of Operations Research (in press)

Ph. D Thesis summary, see other reference on ORBI

Detailed reference viewed: 26 (3 ULiège)
Full Text
See detailA Comparative Study of Labeling Algorithms within the Branch-and-Price Framework for Vehicle Routing with Time Windows
Michelini, Stefano ULiege

Doctoral thesis (2018)

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known extension of the Vehicle Routing Problem, one of the oldest and most studied problems in combinatorial optimization. The VRPTW ... [more ▼]

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known extension of the Vehicle Routing Problem, one of the oldest and most studied problems in combinatorial optimization. The VRPTW consists in finding an optimal set of routes for a fleet of vehicles based in a single depot in order to service a set of customers. Each customer is associated with a time window, which specifies the earliest and the latest possible service start times. Time windows are a natural feature of a number of applications, such as postal deliveries, grocery deliveries, or school bus routing. In addition to the VRPTW, we consider a variant of this problem where the aim is to minimize the total route duration, instead of just the total travel time. Thus, the waiting times that are incurred by vehicles before they can service a customer are taken into account in the objective function of the problem. This aspect is relevant in applications where waiting times bear an implicit cost, such as when the vehicles are rented by the distribution company, or when they consume energy during idle times, as in the case of refrigerated trucks delivering perishable goods. Branch-and-Price (BP) is one of the most effective and commonly used exact methodologies for solving routing problems. In recent years, several studies have investigated advanced labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Being able to solve this subproblem efficiently is crucial, since it is a major bottleneck for the performance of the BP procedure. Each of these methods uses a certain strategy to relax the elementarity constraints of the pricing problem in order to accelerate its solution. In this study, we investigate the performances of several such methods within a BP framework. In order to perform rigorous comparisons, we first parametrize several algorithmic components. Then, we search for good parameter configurations for each algorithm with a tool for automated parameter tuning. Finally, we run the best configuration found for each algorithm on benchmark instances and analyze the results with statistical tests. Our results show in particular that a class of hybrid algorithms, where multiple customer sets are used to control the relaxation of the elementarity conditions, rather than a single one, outperforms all the others. [less ▲]

Detailed reference viewed: 83 (23 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: 26 (5 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: 65 (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)
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: 73 (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)
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: 96 (6 ULiège)
Full Text
Peer Reviewed
See detailExact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege 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: 42 (6 ULiège)
Full Text
Peer Reviewed
See detailExact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time
Michelini, Stefano ULiege; Arda, Yasemin ULiege; Crama, Yves ULiege 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: 110 (23 ULiège)