Gilbert Laporte
RetourPublications
Cahiers du GERAD
In 1960, Ailsa Land and Alison Doig published the first linear programming-based branch-and-bound algorithm for the solution of mixed integer linear progra...
référence BibTeX
The Network Design Problem with Vulnerability Constraints and Probabilistic Edge Reliability (NDPVC-PER) is an extension of the NDPVC obtained by additionall...
référence BibTeX
In July 2022, I received the EURO Gold medal at the 32nd EURO Conference held in Espoo, Finland. On this occasion I was asked to deliver a 30-minute presenta...
référence BibTeX
In e-commerce warehouses, online retailers increase their efficiency by using a mixed-shelves (or scattered storage) concept, where unit loads are purposeful...
référence BibTeXThe design of rapid transit networks
Metros and other rapid transit systems increase the mobility of urban populations while decreasing congestion and pollution. There are now 187 cities with a ...
référence BibTeX
This paper introduces two classes of location problems with interconnected facilities. These problems differ from classical location problems in the sense ...
référence BibTeXThe impact of synchronizing drivers breaks and recharging operations for electric vehicles
Electric commercial vehicles (ECVs) are gaining importance as they are seen to provide a sustainable mean of transportation. However, practitioners still see...
référence BibTeX
This paper reviews the literature on vehicle routing problems and location-routing problems with intermediate stops. Besides providing concise paper excerpts...
référence BibTeX
The purpose of this paper is to develop a fast heuristic called FastCARP for the solution of very large-scale capacitated arc routing problems, with or witho...
référence BibTeXDesigning sustainable mid-haul logistics networks with intra-route multi-resource facilities
Location-routing problems (LRPs) with intra-route facilities have recently gained the attention of researchers and practitioners. Intra-route facilities are ...
référence BibTeXComputational comparison of several algorithms for the minimum cost perfect matching problem
The aim of this paper is to computationally compare several algorithms for the Minimum Cost Perfect Matching Problem on an undirected graph. Our work is moti...
référence BibTeX
This paper introduces the pickup and delivery problem with time windows and handling operations. In this problem, the loading compartment of a vehicle is mod...
référence BibTeX
We model and solve the problem of sequencing a set of jobs with specified processing times and tool requirements on a set of identical parallel machines. D...
référence BibTeX
This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loade...
référence BibTeXThe Tube Challenge
The Tube Challenge consists of visiting all stations of the London Underground in the least possible time. The competition started in 1959 and the current r...
référence BibTeX
In this article, we solve the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading. LIFO loading minimizes handling while unloa...
référence BibTeX
This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and last-in-first-out (LIFO) loading constr...
référence BibTeXScheduling Issues in Vehicle Routing
Scheduling often plays an important role in vehicle routing. This paper describes several applications in which the author has been involved in recent years...
référence BibTeXPlanning Rapid Transit Networks
Le but de cet article est de décrire et de résoudre un nouveau et important problème auquel font face les compagnies maritimes spécialisées dans le transport...
référence BibTeX
The purpose of this paper is to present and solve a new, important planning problem faced by many shipping companies dealing with the transport of bulk produ...
référence BibTeX
The Traveling Salesman Problem and the Vehicle Routing Problem are two of the most popular problems in the field of combinatorial optimization. The purpose ...
référence BibTeXFifty Years of Vehicle Routing
The <i>Vehicle routing Problem</i> (VRP) was introduced 50 years ago by Dantzig and Ramser under the title "The Truck Dispatching Problem". The study of the ...
référence BibTeX
In the <i>Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows</i>, the set of customers is the union of <i>delivery customers</i> and...
référence BibTeX
The <i>Generalized Vehicle Routing Problem</i> (GVRP) is an extension of the classical <i>Vehicle Routing Problem</i> (VRP) in which the vertex set is partit...
référence BibTeX
We compare the effectiveness and efficiency of alternative operational dispatching policies that are integrated into the design phase of a circular material ...
référence BibTeX
Frequency hopping is a feature in GSM (Global System for Mobile Communications) cellular systems in which a frequency carrying the communication rapidly chan...
référence BibTeX
This paper proposes a construction heuristic and an adaptive large neighborhood search heuristic for the technician and task scheduling problem arising in a ...
référence BibTeXA Continuous Analysis Framework for the Solution of Location-Allocation Problems with Dense Demand
Location-allocation problems arise in several contexts, including supply chain and data mining. In its most common interpretation, the basic problem consists...
référence BibTeX
The aim of this paper is to propose a model for the design of a robust rapid transit network. In this paper, a network is said to be robust when the effect o...
référence BibTeX
This paper describes a new heuristic for the well-known <i>Undirected Rural Postman Problem</i>. It consists of two steps: it first constructs a partial so...
référence BibTeX
When constructing a metro alignment under a historical city centre, it is important to generate a cost effective path while maintaining a minimum distance be...
référence BibTeX
In the <i>Vehicle Routing Problem </i> (VRP), the aim is to design a set of <i>m</i> minimum cost vehicle routes through <i>n</i> customer locations, so that...
référence BibTeX
The <i>Capacitated Arc Routing Problem</i> (CARP) consists of determining a set of least cost capacitated vehicle routes servicing a set of arcs. In this p...
référence BibTeX
In One-to-Many-to-One Single Vehicle Pickup and Delivery Problems a vehicle based at the depot must make deliveries and pickups at customers locations befor...
référence BibTeX
In modern transportation systems, the potential for further decreasing the costs of fulfilling customer requests is severely limited while market competitio...
référence BibTeX
The <i>Dial-a-Ride Problem</i> (DARP) consists of designing vehicle routes and schedules for <i>n</i> users who specify pickup and delivery requests between...
référence BibTeX
In one-to-one <i>Pickup and Delivery Problems</i> (PDPs), the aim is to design a set of least cost vehicle routes starting and ending at a common depot in o...
référence BibTeXA Review and Comparative Analysis of Several Asymmetric Travelling Salesman Problem Formulations
In this survey, a classification of twenty-seven Asymmetric Traveling Salesman Problem (ATSP) formulations is presented. The strength of their LP relaxation...
référence BibTeX
This paper considers the swapping problem on a tree. In this problem at most one object of some type is available at each vertex, and each vertex also reque...
référence BibTeX
Earth observation satellites are platforms equipped with optical instruments that orbit the Earth in order to take photographs of specific areas at the requ...
référence BibTeX
This paper examines the plant location problem under the objective of maximizing return-on-investment. However, in place of the standard assumption that all...
référence BibTeX
Several variants and generalizations of the Or-opt heuristic for the <i>Symmetric Traveling Salesman Problem</i> are developed and compared on random and pla...
référence BibTeX
This article reviews some of the best metaheuristics proposed in recent years for the Vehicle Routing Problem. These are based on local search, on populatio...
référence BibTeX
The problem of determining a shortest loop incident to each cell of a block layout is considered. A compact formulation is developed for this problem and a ...
référence BibTeXExact and Heuristic Procedures for the Material Handling Circular Flow Path Design Problem
In this study we develop optimization, decomposition, and heuristic procedures to design a unidirectional loop flow pattern along with the pickup and delive...
référence BibTeX
A sizeable proportion of manufacturing expenses can be attributed to facility layout and material handling. Facility layout decisions involve designing the ...
référence BibTeX
In the <i>m</i>-Peripatetic Salesman Problem</i> (<i>m</i>-PSP) the aim is to determine <i>m</i> edge disjoint Hamiltonian cycles of minimum total cost on a ...
référence BibTeX
This chapter describes some of the most important models and algorithms for the classical vehicle routing problem and for several families of arc routing pr...
référence BibTeX
Corrected Miller-Tucker-Zemlin type subtour elimination constraints for the Capacitated Vehicle Routing Problem are presented.
référence BibTeX
This article describes a tabu search heuristic for the <i>Dial-a-Ride Problem</i> with the following characteristics. Users specify transportation requests ...
référence BibTeX
The <i>Dial-a-Ride Problem</i> (DARP) consists of designing vehicle routes and schedules for <i>n</i> users who specify pick-up and drop-off requests betwee...
référence BibTeX
In the undirected <i>Hierarchical Chinese Postman Problem</i> (HCPP), the edges of a graph are partitioned into clusters and must be serviced while respecti...
référence BibTeX
The <i>Job Sequencing and Tool Switching Problem</i> (SSP) involves optimally sequencing jobs and assigning tools to a capacitated magazine in order to mini...
référence BibTeX
This article considers the (1|<i>X<sub>p</sub></i>-medianoid problem on a network <i>N</i>=(<i>V,E</i>) with vertex and edge demands. There are already <i>p...
référence BibTeX
In the <i>Maximum Cardinality Bin Packing Problem</i>, we are given <i>m</i> bins of capacity <i>c</i> and <i>n</i> items of weights <i>w<sub>i</sub></i> (...
référence BibTeX
This article reviews ten of the most important tabu search heuristics for the vehicle routing problem. Some of the main tabu search features are first desc...
référence BibTeX
The purpose of this article is to describe several applications of the Clustered Traveling Salesman Problem arising in areas as diverse as vehicle routing, ...
référence BibTeX
This paper investigates several questions related to the location of facilities in multi-storey buildings in the presence of lifts. Where should facilities ...
référence BibTeXA General Multi-Shift Scheduling System
Rotating work schedules are encountered in several industries and public sector organizations where work is carried out 24 hours a day, seven days a week. ...
référence BibTeXAmbulance Location and Relocation Models
This article traces the evolution of ambulance location and relocation models proposed over the past thirty years. The models are classified in two main ca...
référence BibTeX
The Esau-Williams algorithm is one of the best known heuristics for the Capacitated Minimum Spanning Tree Problem. This research note describes a simple en...
référence BibTeX
This article reports on some recent algorithmic development for the <i>Rural Postman Problem</i> (CPP) and for the <i>Capacitated Arc Routing Problem</i> (C...
référence BibTeXLocation-Arc Routing Problems
<i>Location-Arc Routing Problems</i> (LARPs) are encountered in contexts where it is necessary to simultaneously determine a traversal of a subset of edges ...
référence BibTeX
In several arc routing problems, it is necessary to take turn penalties into account when designing a solution. Traditionally, this is done through a trans...
référence BibTeX
In this paper, we prove that the maximum <i>k</i>-club problem defined on an undirected graph is NP-hard. We also give an integer programming formulation f...
référence BibTeX
This article is a survey of heuristics for the <i>Vehicle Routing Problem</i>. It is divided into two parts: classical and modern heuristics. The first pa...
référence BibTeX
Over the last thirty-five years several heuristics have been proposed for the <i>Vehicle Routing problem</i>. This article reviews the main classical heuris...
référence BibTeX
In recent years several <i>metaheuristics</i> have been proposed for the <i>Vehicle Routing Problem</i>. This article reviews the main metaheuristics for th...
référence BibTeX
The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties ...
référence BibTeX
Il est généralement reconnu que le processus de découpage électoral doit être à l'abri du gerrymandering et de l'intervention politique. L'utilisation de mé...
référence BibTeX
The purpose of this article is to formulate and solve a shortest loop problem associated with the design of material flow handling systems in factories. Th...
référence BibTeX
In a graph <i>G</i>, a <i>k-club</i> is a vertex set inducing a subgraph of diameter <i>k</i>. These structures play an important role in several applicati...
référence BibTeX
Rotating schedules are commonly used in a number of industries and public services where employees work round the clock, seven days a week. Several rules g...
référence BibTeX
In recent years, there have been several important algorithmic developments for the traveling salesman problem and the vehicle routing problem. These incl...
référence BibTeX
In recent years, several advances have been made towards the solution of stochastic vehicle routing problems (SVRPs). In particular, the Integer <i>L</i>-Sh...
référence BibTeX
This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacita...
référence BibTeX
This article describes the results of a study aimed at improving linen delivery operations in a large teaching hospital in Montreal. Improvements over the p...
référence BibTeX
This article considers a tool loading problem whose objective is to minimize the number of tool switches over time in order to process several parts on a fl...
référence BibTeXPath, Tree and Cycle Location
<i>Extensive facilities</i> are structures that are too large to be considered as single points. In the first part of this paper we propose integer program...
référence BibTeXCovering a Graph with Cycles
This article describes a lower bounding procedure and heuristics for the <i>Cycle Cover Problem</i> which consists of determining a least cost cover of an u...
référence BibTeX
This paper contains some 80 annotated references on the vehicle routing problem. The titles are organized as follows: 1) the classical VRP with capacity an...
référence BibTeX
In recent years, there have been several important algorithmic developments for the traveling salesman problem and the vehicle routing problem. These inclu...
référence BibTeX
The purpose of this paper is to develop optimal tool partitioning policies and strip sequencing strategies for a class of flexible manufacturing problems. ...
référence BibTeX
In the Generalized Traveling Salesman Problem (GTSP), the aim is to determine a least cost Hamiltonian circuit or cycle through several clusters of vertic...
référence BibTeX
In this paper we derive lower bounds on the size of a minimum cover of a graph <i>G</i> by computing packings of edges, odd cycles and cliques of <i>G</i> o...
référence BibTeX
Multiobjective decision making problems occur in a variety of transportation planning settings. These are often ill-defined and may involve several players...
référence BibTeX
In 1986, Carter published a survey of papers on practical examination timetabling. In the intervening years, there have been a number of new applications, ...
référence BibTeX
The purpose of this paper is to develop optimal tool partitioning policies and strip sequencing strategies for a class of flexible manufacturing problems su...
référence BibTeX
Examination timetabling is an important operational problem in many schools, colleges and universities. The authors have developed a computerized examinatio...
référence BibTeX
This paper describes strip sequencing models for large scale traveling salesman problems arising in flexible manufacturing operations in two or three discre...
référence BibTeX
It is well known that several combinatorial optimization problems can be nicely and readily modeled as an appropriate quadratic 0-1 function to be optimized...
référence BibTeX
In the Dual Bin Packing Problem (DBP), there are an unlimited number of bins of identical capacity, and unsplittable items of given weights. The aim is to ...
référence BibTeX
The purpose of this paper is to formulate and solve an optimization problem arising in the operations of a numerical control machine such as a punch press. ...
référence BibTeX
Given a binary matrix <i>E</i>, the Seriation Problem consists of determining a permutation of the rows of <i>E</i> minimizing the sum over all columns of t...
référence BibTeX
The majority of the examination timetabling software programs available today suffer from one of the following drawbacks: either the techniques are not very...
référence BibTeX
In this paper, optimal strip strategies are developed for a variety of two-dimensional and three-dimensional sequencing problems arising in flexible manufac...
référence BibTeX
In this paper, the expected distance between two uniformly distributed random points in a rectangle or in a rectangular parallelepiped is computed under thr...
référence BibTeX
Examination scheduling is a problem in virtually every high school, college and university. The basic challenge is to schedule examinations over a limited ...
référence BibTeX
The purpose of this paper is to describe a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algori...
référence BibTeX
This paper describes a domain criterion for a multicriteria problem, given a single decision maker. It then outlines possibilities for aggregating individua...
référence BibTeX
In this paper, the problem of optimally locating the numbers around a dart board is investigated. The objective considered is risk maximization. Under diffe...
référence BibTeX
This paper considers a flexible manufacturing system for several products, each requiring a number of sequential non-preemptive tasks, some of which may be...
référence BibTeX
This paper shows how the subtour elimination constraints developed by Miller, Tucker and Zemlin for the traveling salesman problem can be improved and exten...
référence BibTeX
In this paper, we present general formulations for the stochastic vehicle routing problem with capacity restrictions in which the <i>m</i> vehicle tours hav...
référence BibTeX
Given a weighted graph with profits associated with the vertices, the selective travelling salesman problem (or orienteering problem) consists of selecting ...
référence BibTeX
This paper describes a family of stochastic location-routing problems which consist of simultaneously locating a depot among a set of potential sites, of det...
référence BibTeX
In this paper we analyze the problem of finding the trading area for a facility on a linear market. Given the objective of maximizing profit, we first build...
référence BibTeX
This paper examines a class of asymmetrical multi-depot vehicle routing problems and location-routing problems, under capacity or maximum cost restrictions. ...
référence BibTeX
In this paper, an extension of the classical scheduling problem is considered. It is assumed that tasks are processed on parallel processors, available at d...
référence BibTeXLocation-Routing Problems
Location-routing problems involve simultaneously locating a number of facilities among candidate sites and establishing delivery routes to a set of users in ...
référence BibTeXVehicle Routing with Full Loads
This paper considers a vehicle routing problem with full loads and time limit constraints. This problem can be formulated as an asymmetrical travelling sale...
référence BibTeX
Hydraulic turbine runners are used in electricity generation. These consist of a cylinder around which are welded, at regular spacings, a number of blades w...
référence BibTeX
In this paper the authors describe a heuristic principle for the solution of an important class of problems. Using real-world examples, it is then shown how...
référence BibTeX
Post box collection constitutes a complex and costly operation in most postal services. The authors recently undertook a study aimed at improving this opera...
référence BibTeX
This paper describes a vehicle flow model for a two-echelon location-routing problem involving deliveries from primary to secondary facilities and from secon...
référence BibTeXA Branch-and-Bound Algorithm for the Asymetrical Distance Constrained Vehicle Routing Problem
The aim of this paper is to develop an exact algorithm for the asymmetrical distance constrained vehicle routing problem. The problem is solved by means of ...
référence BibTeX
This paper describes an exact algorithm for a general class of asymmetrical vehicle routing problems. Vehicle routes start and end at a central depot. Visi...
référence BibTeX
This paper considers the archeological seriation problem defined over incidence matrices. Two procedures adapted from interchange algorithms for the travell...
référence BibTeX
Let n facilities be located on a bounded linear market and assume that demand for a homogenous commodity is uniformly distributed along that market. Initial...
référence BibTeX
This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian cirnui...
référence BibTeXAn Optimal Flow Circulation Algorithm for the Asymmetrical Multiple Travelling Salesman Problem
This paper describes an exact algorithm for the asymmetrical multiple travelling salesman problem. The problem is solved by branch and bound and a flow circ...
référence BibTeX
This paper deals with the optimal location of post boxes in an urban or in a rural environment. The problem consists of selecting sites for post boxes which...
référence BibTeX
This paper presents an integer linear programming formulation for the symmetrical capacitated vehicle routing problem (CVRP). This formulation includes degr...
référence BibTeX
Cet article décrit dive3rs types d'horaires de travail en vigueur dans les entreprises et les services publics, ainsi que les principales méthodes de recherc...
référence BibTeX
This paper examines a family of permutation problems on 0-1 matrices. These problems arise in scheduling and in archaeological seriation. Three exact algor...
référence BibTeX
This paper presents a survey of exact algorithms for various types of vehicle routing problems. Algorithms are divided into three main categories: direct s...
référence BibTeXLe traitement des exigences rigides et souples dans certains problèmes d'optimisation combinatoire
Le présent article décrit des méthodes algorithmiques de traitement des exigences rigides et souples dans certains problèmes complexes d'optimisation combina...
référence BibTeX
This paper examines some properties of generalized subtour elimination constraints and connectivity constraints used in a variety of routing problems.
référence BibTeX
People who attend several meetings on the same day often have unusable pieces of free time between meetings. These can be reduced or eliminated through bett...
référence BibTeX
In some universities, complete course schedules are made available to students at the time of registration. Typically these schedules give the room number, ...
référence BibTeX
In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construc...
référence BibTeX
The aim of this paper is to develop an exact algorithm for the asymmetrical capacitated vehicle routing problem, i.e. the multiple travelling salesman proble...
référence BibTeX
Ce rapport décrit un modèle de planification tactique pour l'amélioration de l'industrie du camionnage au Canada. après une brève description du problème, o...
référence BibTeXFinding the Shortest Hamiltonian Circuit Through n Clusters: A Lagrangean Relaxation Approach
This paper deals with a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters,...
référence BibTeX
This paper describes algorithmic approaches for dealing with fuzziness in some highly structured combinatorial problems. A general framework is described an...
référence BibTeX
This paper describes an integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints. The method uses const...
référence BibTeX
This paper provides an integer linear programming formulation and an exact algorithm for a class of multidepot vehicle routing problems. This formulation co...
référence BibTeX
This paper provides integer linear programming formulations for three types of vehicle routing problems. Appropriate relaxations of these formulations lend ...
référence BibTeX
This paper provides an integer linear programming formulation for a class of multidepot vehicle routing problems. This formulation contains degree constrain...
référence BibTeX
Le problème du voyageur de commerce (PVC) symétrique consiste à déterminer le cycle le plus court passant exactement une fois par chacun des noeuds d'un grap...
référence BibTeX
This paper consider the problem of determining the shortest circuit or cycle in a graph containing n nodes and such that (i) each of k nodes (k ≤ n) i...
référence BibTeX
This paper shows the existence of a class of valid inequalities for two types of vehicle routing problems. These inequalities constitute a generalization of...
référence BibTeX
Let G = (N,E) be an undirected graph where N is the set of nodes and E, the set of edges. Let C be a symmetrical distance matrix defined on N<sup>2</sup> an...
référence BibTeX
This paper describes an automatic procedure for constructing examination timetables in universities. The program produces schedules in which there are no co...
référence BibTeX
This paper considers a version of the vehicle scheduling problem (VSP) in which a non-negative weight is assigned to each city to be visited and where all ve...
référence BibTeX
This paper considers a version of the vehicle routing problem in which a non-negative weight is assigned to each city to be visited and where all vehicles ar...
référence BibTeX
This paper considers a version of the vehicle routing problem in which all vehicles are identical and where the distance travelled by any vehicle may not exc...
référence BibTeX
When an electoral map is set up, various socio-economical, political and geographical parameters are taken into consideration. To evaluate the importance of...
référence BibTeX