Personne : Coelho, Leandro C.
En cours de chargement...
Date de naissance
Projets de recherche
Nom de famille
Université Laval. Département d'opérations et systèmes de décision
Résultats de recherche
Voici les éléments 1 - 10 sur 19
- PublicationAccès libreOrder picking problems under weight, fragility, and category constraints(Taylor & Francis, 2016-10-27) Chabot, Thomas; Lahyani, Rahma; Renaud, Jacques; Coelho, Leandro C.Warehouse order picking activities are among the ones that impact the most the bottom lines of warehouses. They are known to often account for more than half of the total warehousing costs. New practices and innovations generate new challenges for managers and open new research avenues. Many practical constraints arising in real-life have often been neglected in the scientific literature. We introduce, model and solve a rich order picking problem under weight, fragility and category constraints, motivated by our observation of a real-life application arising in the grocery retail industry. This difficult warehousing problem combines complex picking and routing decisions under the objective of minimising the distance travelled. We first provide a full description of the warehouse design which enables us to algebraically compute the distances between all pairs of products. We then propose two distinct mathematical models to formulate the problem. We develop five heuristic methods, including extensions of the classical largest gap, mid-point, S-shape and combined heuristics. The fifth one is an implementation of the powerful adaptive large neighbourhood search algorithm specifically designed for the problem at hand. We then implement a branch-and-cut algorithm and cutting planes to solve the two formulations. The performance of the proposed solution methods is assessed on a newly generated and realistic test bed containing up to 100 pickups and 7 aisles. We compare the bounds provided by the two formulations. Our in-depth analysis shows which formulation tends to perform better. Extensive computational experiments confirm the efficiency of the ALNS metaheuristic and derive some important insights for managing order picking in this kind of warehouses.
- PublicationAccès libreSolving the vehicle routing problem with lunch break arising in the furniture delivery industry(Palgrave, 2016-09-16) Gagliardi, Jean-Philippe; Ruiz, Angel; Renaud, Jacques; Coelho, Leandro C.In this paper, we solve the Vehicle Routing Problem with Lunch Break (VRPLB), which arises when drivers must take pauses during their shift, for example, for lunch breaks. Driver breaks have already been considered in long haul transportation when drivers must rest during their travel, but the underlying optimization problem remains difficult and few contributions can be found for less than truckload and last mile distribution contexts. This problem, which appears in the furniture delivery industry, includes rich features such as time windows and heterogeneous vehicles. In this paper, we evaluate the performance of a new mathematical formulation for the VRPLB and of a fast and high performing heuristic. The mixed integer linear programming formulation has the disadvantage of roughly doubling the number of nodes, and thus significantly increasing the size of the distance matrix and the number of variables. Consequently, standard branch-and-bound algorithms are only capable of solving small-sized instances. In order to tackle large instances provided by an industrial partner, we propose a fast multi-start randomized local search heuristic tailored for the VRPLB, which is shown to be very efficient. Through a series of computational experiments, we show that solving the VRPLB without explicitly considering the pauses during the optimization process can lead to a number of infeasibilities. These results demonstrate the importance of integrating drivers pauses in the resolution process.
- PublicationAccès libreRoad-based goods transportation : a survey of real-world logistics applications from 2000 to 2015(Taylor & Francis, 2016-04-04) Renaud, Jacques; Coelho, Leandro C.; Laporte, GilbertThe vehicle routing problem has been widely studied from a technical point of view for more than 50 years. Many of its variants are rooted in practical settings. This paper provides a survey of the main real-life applications of road-based goods transportation over the past 15 years. It reviews papers in the areas of oil, gas and fuel transportation, retail, waste collection and management, mail and package delivery and food distribution. Some perspectives on future research and applications are discussed.
- PublicationRestreintThe traveling backpacker problem : a computational comparison of two formulations(Springer, 2017-03-10) Nakamura, Katia Y.; Renaud, Jacques; Coelho, Leandro C.; Nascimento, Mariá C. V.The rise of low-cost airlines has influenced the tourism industry, particularly in trips known as backpacking. This form of traveling is mostly adopted by people on a tight budget, intending to visit a large number of touristic attractions. In the Traveling Backpacker Problem (TBP), the objective is to find the best sequence of visits, so as to minimize the total travel cost. This problem was first modeled as a routing problem. Nevertheless, for small-sized instances, an exact solver could not find any feasible solutions. In this paper, we propose a new formulation for the TBP, which is based on a network flow representation of the problem. We tested both models using a state-of-the-art MIP solver on instances generated from real data obtained from low-cost airlines. Computational experiments indicate that the network flow-based formulation outperforms the routing-based formulation and can yield high-quality solutions for instances of realistic size.
- PublicationAccès libreDetermining time-dependent minimum cost paths under several objectives(Elsevier, 2019-01-17) Heni, Hamza; Renaud, Jacques; Coelho, Leandro C.As the largest contributor to greenhouse gas (GHG) emissions in the transportation sector, road freight transportation is the focus of numerous strategies to tackle increased pollution. One way to reduce emissions is to consider congestion and being able to route traffic around it. In this paper we study time-dependent minimum cost paths under several objectives (TDMCP-SO), in which the objective function comprises GHG emissions, driver and congestion costs. Travel costs are impacted by traffic due to changing congestion levels depending on the time of the day, vehicle types and carried load. We also develop time-dependent lower and upper bounds, which are both accurate and fast to compute. Computational experiments are performed on real-life instances that incorporate the variation of traffic throughout the day, by adapting Dijkstra’s label-setting algorithm according to different cost computation methods. We show that explicitly considering first-in, first-out (FIFO) consistency using time-varying speeds allows the efficient computation of tight time-dependent bounds. Our computational results demonstrate that the TDMCP-SO is more difficult to solve to optimality but the proposed algorithm is shown to be robust and efficient in reducing the total cost even for large instances in an environment of varying speeds, outperforming those based on the link travel time model and on the smoothing method according to each optimization objective, flexible departure times, and different load patterns.
- PublicationAccès libreThe time-dependent shortest path and vehicle routing problem(Taylor & Francis Group, 2021-09-11) Jaballah, Rabie; Veenstra, Marjolein; Renaud, Jacques; Coelho, Leandro C.We introduce the time-dependent shortest path and vehicle routing problem. In this problem, a set of homogeneous vehicles is used to visit a set of customer locations dispersed over a very large network where the travel times are time-dependent and therefore the shortest path between two locations may change over time. The aim of the problem is to simultaneously determine the sequence in which the customer locations are visited and the arcs traveled on the paths between each pair of consecutively visited customers, such that the total travel time is minimized. We are the first to formally define and solve this fully integrated problem, providing tight bounds to it. We then propose a dynamic time-dependent shortest path algorithm embedded within a simulated annealing metaheuristic to efficiently solve the problem. We also propose a variant of the algorithm where some time-dependent shortest paths are precomputed. We test our formulations and algorithms on a set of real-life instances generated from a dataset of the road network in Québec City, Canada. Our results indicate that the resulting models are too large to be solved even for small instances. However, the obtained bounds show that the developed simulated annealing heuristic performs very well. We also demonstrate that neglecting time-dependent information on traffic leads to imprecise estimation of the traveling time. Moreover, the results show the importance of solving the shortest paths and routing problems simultaneously, as using a set of precomputed shortest paths leads to slightly worse solutions. This work adds new research avenues to city logistics and congestion studies.
- PublicationAccès libreMathematical Model, Heuristics and Exact Method for Order Picking in Narrow Aisles(Basingstoke Basingstoke Stockton Palgrave, 2018-07-01) Chabot, Thomas; Côté, Jean-François; Renaud, Jacques; Coelho, Leandro C.Order picking is one of the most challenging operations in distribution centre management and one of the most important sources of costs. One way to reduce the lead time and associated costs is to minimise the total amount of work for collecting all orders. This paper is motivated by a collaboration with an industrial partner who delivers furniture and electronic equipment. We have modelled their narrow aisles order picking problem as a vehicle routing problem through a series of distance transformations between all pairs of locations. Security issues arising when working on narrow aisles impose an extra layer of difficulty when determining the routes. We show that these security measures and the operator equipment allow us to decompose the problem per aisle. In other words, if one has to pick orders from three aisles in the warehouse, it is possible to decompose the problem and create three different instances of the picking problem. Our approach yields an exact representation of all possible picking sequences. We also show that neglecting 2D aspects and solving the problem over a 1D warehouse yields significant difference in the solutions, which are then suboptimal for the real 2D case. We have solved a large set of instances reproducing realistic configurations using a combination of heuristics and an exact algorithm, minimising the total distance travelled for picking all items. Through extensive computational experiments, we identify which of our methods are better suited for each aisle configuration. We also compare our solutions with those obtained by the company order picking procedures, showing that improvements can be achieved by using our approach
- PublicationAccès libreService level, cost and environmental optimization of collaborative transportation(Elsevier, 2017-12-09) Legault-Michaud, Ariane; Bouchard, Florence; Chabot, Thomas; Renaud, Jacques; Coelho, Leandro C.Less than truckload is an important type of road-based transportation. Based on real data and on a collaboration with industry, we show that a collaborative approach between companies offers important benefits. We propose to develop partnerships between shipping companies and to synchronize their shipments. Four operational collaborative schemes with different objectives are developed. The first one focuses on minimizing shipping costs for shippers. The second and third ones minimize the carrier’s costs and the environmental cost, respectively. The fourth one is a combination of all three. The results of our computational experiments demonstrate that collaboration lead to significant cost reductions.
- PublicationAccès libreIntegrated production-distribution systems : Trends and perspectives(Scientific Electronic Library Online (SciELO Brazil), 2021-04-21) Darvish, Maryam; Renaud, Jacques; Coelho, Leandro C.; Kidd, Martin P.During the last two decades, integrated production-distribution problems have attracted a great deal of attention in the operations research literature. Within a short period, a large number of papers have been published and the field has expanded dramatically. The purpose of this paper is to provide a comprehensive review of the existing literature by classifying the existing models into several different categories based on multiple characteristics. The paper also discusses some trends and list promising avenues for future research.
- PublicationAccès libreQuadratic assignment problem variants : a survey and an effective parallel memetic iterated tabu search(2020-11-26) Silva, Allyson; Darvish, Maryam; Coelho, Leandro C.In the Quadratic Assignment Problem (QAP), facilities are assigned to sites in order to minimize interactions between pairs of facilities. Although easy to define, it is among the hardest problems in combinatorial optimization, due to its non-linear nature. After decades of research on the QAP, many variants of this problem arose to deal with different applications. Along with the QAP, we consider four variants – the Quadratic Bottleneck Assignment Problem, the Biquadratic Assignment Problem, the Quadratic Semi-Assignment Problem, and the Generalized QAP – and develop a single framework to solve them all. Our parallel memetic iterated tabu search (PMITS) extends the most successful heuristics to solve the QAP. It combines the diversification phase of generating new local optima found after solutions modified by a new crossover operator that is biased towards one of the parents, with the intensification phase of an effective tabu search which uses a simplified tabu list structure to reduce the number of parameters and a new long-term memory that saves solutions previously visited to speed up the search. Solutions are improved concurrently using parallelism, and a convergence criterion determines whether the search stops according to the best solutions in each parallel search. Computational experiments using the hardest benchmark instances from the literature attest the effectiveness of the PMITS, showing its competitiveness when compared to the state-of-the-art methods, sequential and parallel, to solve the QAP. We also show that PMITS significantly outperforms the best methods found for all four variants of the QAP, significantly updating their literature.