Fifty Years of Vehicle Routing Laporte, Gilbert
Transportation science,
11/2009, Letnik:
43, Številka:
4
Journal Article
Recenzirano
The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title "The Truck Dispatching Problem." The study of the VRP has given rise to major developments in the ...fields of exact algorithms and heuristics. In particular, highly sophisticated exact mathematical programming decomposition algorithms and powerful metaheuristics for the VRP have been put forward in recent years. The purpose of this article is to provide a brief account of this development.
•An extensive analysis of factors affecting fuel consumption is provided.•Freight transportation vehicle emission models are reviewed.•Routing problems with fuel consumption components are ...investigated.•A systematic review of 58 publications on green logistics is carried out.
Road freight transportation is a major contributor to carbon dioxide equivalent emissions. Reducing these emissions in transportation route planning requires an understanding of vehicle emission models and their inclusion into the existing optimization methods. This paper provides a review of recent research on green road freight transportation.
This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm ...applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.
The inventory-routing problem (IRP) dates back 30 years. It can be described as the combination of vehicle-routing and inventory management problems, in which a supplier has to deliver products to a ...number of geographically dispersed customers, subject to side constraints. It provides integrated logistics solutions by simultaneously optimizing inventory management, vehicle routing, and delivery scheduling. Some exact algorithms and several powerful metaheuristic and matheuristic approaches have been developed for this class of problems, especially in recent years. The purpose of this article is to provide a comprehensive review of this literature, based on a new classification of the problem. We categorize IRPs with respect to their structural variants and the availability of information on customer demand.
•Aisla H. Land made several important contributions to the Traveling Salesman Problem•She contributed to the development of branch-and-cut and cut-and-price for this problem•This note presents some ...of her main contributions dating from 1955 and 1979
Ailsa H. Land, who received the 2021 EURO Gold Medal, made some important contributions to the study of the Traveling Salesman Problem, which were published in a 1955 journal article and in a 1979 working paper. The purpose of this introductory note is to describe these contributions.
•We study route and speed planning for autonomous trucks.•The traffic speed is assumed to be a random variable.•We aim to minimize the expected cost of fuel, emissions, driver and delay.•Several ...two-stage stochastic programming formulations are presented.•The average savings in cost compared to using a deterministic model is 7.4%.
Autonomous vehicles, and in particular autonomous trucks (ATs), are an emerging technology that is becoming a reality in the transportation sector. This paper addresses the problem of optimizing the routes and the speeds of ATs making deliveries under uncertain traffic conditions. The aim is to reduce the cost of emissions, fuel consumption and travel times. The traffic conditions are represented by a discrete set of scenarios, using which the problem is modeled in the form of two-stage stochastic programming formulations using two different recourse strategies. The strategies differ in the amount of information available during the decision making process. Computational results show the added value of stochastic modeling over a deterministic approach and the quantified benefits of optimizing speed.
Maritime transport is the backbone of international trade and globalization. Maritime transport research can be roughly divided into two categories, namely the shipping side and the port side. Most ...of the classic approaches adopted to address practical problems in these research topics are based on long-term observations and expert knowledge, while few of them are based on historical data accumulated from practice. In recent years, emerging approaches, which we refer to as machine learning and deep learning techniques in this essay, have been receiving a wider attention to solve practical problems. As a relatively conservative industry, there are some initial trials of applying the emerging approaches to solve practical problems in the maritime sector. The objective of this essay is to review the application of emerging approaches to maritime transport research. The main research topics in maritime transport and classic methods developed to solve them are first presented. The introduction of emerging approaches and their suitability to be applied in maritime transport research is then discussed. Related existing studies are then reviewed according to problem settings, main data sources, and emerging approaches adopted. Challenges and solutions in the process are also discussed from the perspectives of data, model, users, and targets. Finally, promising future research directions are identified. This essay is the first to give a comprehensive review of existing studies on developing machine learning and deep learning models together with popular data sources used to address practical problems in maritime transport.
We model and solve the Railway Rapid Transit Network Design and Line Planning (RRTNDLP) problem, which integrates the two first stages in the Railway Planning Process. The model incorporates costs ...relative to the network construction, fleet acquisition, train operation, rolling stock and personnel management. This implies decisions on line frequencies and train capacities since some costs depend on line operation. We assume the existence of an alternative transportation system (e.g. private car, bus, bicycle) competing with the railway system for each origin–destination pair. Passengers choose their transportation mode according to the best travel times. Since the problem is computationally intractable for realistic size instances, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm, which can simultaneously handle the network design and line planning problems considering also rolling stock and personnel planning aspects. The ALNS performance is compared with state-of-the-art commercial solvers on a small-size artificial instance. In a second stream of experiments, the ALNS is used to design a railway rapid transit network in the city of Seville.
•We model and solve the Railway Rapid Transit Network Design and Line Planning (RRTNDLP) problem.•We take into account costs relative to the network construction, fleet acquisition, operation, rolling stock and personnel.•We assume the existence of an alternative transport mode competing with the railway for each origin-destination pair.•We develop an Adaptive Large Neighborhood Search algorithm, which simultaneously solve the network design and line planning problems.•The ALNS performance is compared with state-of-the-art commercial solvers.•We apply the ALNS to areal-size instance concerning the design of a railway rapid transit network in the city of Seville.
•We introduce the minimum cost network design problem in strategic alliances.•We consider transaction costs induced by the formation of the alliance.•We concentrate on bilateral alliances.•Accounting ...for the transaction cost in network design is vital for the alliance.•These transaction costs may even render the collaboration unattractive.
Strategic alliances are established between firms to improve their competitiveness in markets and generally appear in the form of joint ventures. Such collaborative efforts require centralized planning, and the survival of the alliance largely depends on the success of joint planning processes. In this regard, we investigate the opportunities that centralized collaboration can offer to firms when designing their service networks. Apart from the classical fixed and variable costs associated with the network design, we also consider transaction costs induced by the formation of the alliance, which can broadly be defined as cost components related to the coordination and monitoring of the people, efforts and resources. We concentrate on bilateral alliances and develop alternative models for solving their associated network design problem. We also adopt a state-of-the-art heuristic to solve large-scale instances. Our findings confirm that accounting for the transaction cost in network design is vital for the alliance. These transaction costs can be high enough to even render the collaboration unattractive. Hence, careful data collection and model treatment are required before deciding whether to form an alliance.
•Survey of author’s research from 1972 to 2022.•Ten applications are presented.•Conclusions and avenues for future research are drawn.
In July 2022, I received the EURO Gold medal at the 32nd EURO ...Conference held in Espoo, Finland. This paper is based on the presentation I made at the medal award ceremony. It covers 10 topics on which I have worked throughout my career. These are the seriation problem, rotating work schedules, deterministic vehicle routing, stochastic vehicle routing, examination timetabling, districting, waste management, metro network design, green transportation, and humanitarian logistics.
PDF
