References of "Küçükaydın, Hande"
     in
Bookmark and Share    
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)
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
See detailOptimization of the service start time for an elementary shortest path problem with time windows
Küçükaydın, Hande; Arda, Yasemin ULiege; Crama, Yves ULiege

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: 277 (32 ULiège)