Disruption management in vehicle routing and scheduling for road freight transport: a review

Disruption management is an approach to the rescheduling of operations following an unanticipated event occurring that has been applied in a wide range of applications, including airline scheduling and project management. This review focusses on the use of disruption management in vehicle routing and scheduling applied to road freight distribution. The paper discusses the key features of disruption management and examines the relevant objectives and types of disruption that may occur in this context. Different formulations and solution methods are described. A set of relevant papers are summarised and classified according to the type of disruption addressed, the relevant objectives and the solution approach.     

Multifleet routing and multistop flight scheduling for schedule perturbation

Efficient and effective incidental scheduling techniques for schedule perturbation are essential to an airline carrier's operations. This research aims at developing a framework to assist carriers in fleet routing and flight scheduling for schedule perturbations in the operations of multifleet and multistop flights. The framework is based on a basic multifleet schedule perturbation model constructed as a timespace network from which strategic models are developed to research incidental scheduling. These network models are formulated as multiple commodity network flow problems. Lagrangian relaxation with subgradient methods accompanied by the network simplex method, a Lagrangian heuristic and a modified subgradient method are developed to solve the problems. A case study regarding the international operations of a major Taiwan airline carrier is presented.     

Ship routing and scheduling in the new millennium

We review research on ship routing and scheduling and related problems during the new millennium and provide four basic models in this domain. The volume of research in this area about doubles every decade as does the number of research outlets. We have found over a hundred new refereed papers on this topic during the last decade. Problems of wider scope have been addressed as well as more specialized ones. However, complex critical problems remain wide open and provide challenging opportunities for future research.     

Metaheuristics in Combinatorial Optimization

The emergence of metaheuristics for solving difficult combinatorial optimization problems is one of the most notable achievements of the last two decades in operations research. This paper provides an account of the most recent developments in the field and identifies some common issues and trends. Examples of applications are also reported for vehicle routing and scheduling problems.     

Rich routing problems arising in supply chain management

The purpose of this paper is to provide basic models for highly relevant extensions of the classical vehicle routing problem in the context of supply chain management. The classical vehicle routing problem is extended in various ways. We will especially focus on extensions with respect to lotsizing, scheduling, packing, batching, inventory and intermodality. The proposed models allow for a more efficient use of resources, while explicitly taking into account interdependencies among the subproblems. The contribution of this survey is twofold: (i) it provides an overview of recent and suitable literature for the interested scholar and (ii) it presents six integrative models for the above mentioned extensions.     

Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints

Liquefied natural gas (LNG) is natural gas that has been transformed to liquid form for the purpose of transportation, which is mainly done by specially built LNG vessels travelling from the production site to the consumers. We describe a real-life ship routing and scheduling problem from the LNG business, with both inventory and berth capacity constraints at the liquefaction port. We propose a solution method where the routing and scheduling decisions are decomposed. The routing decisions consist of deciding which vessels should service which cargoes and in what sequence. The scheduling decisions are then to decide when to start servicing the cargoes while satisfying inventory and berth capacity constraints. The proposed solution method has been tested on several problem instances based on the real-life problem. The results show that the proposed solution method is well suited to solve this LNG shipping problem.     

Perspectives on practical aspects of truck routing and scheduling

Truck routing and scheduling problems are differentiated from other vehicle routing and scheduling problems and a classification scheme for the former ones is outlined. Many characteristics of practical truck routing and scheduling problems are listed and several aspects are discussed, among them are: soft constraints, demand variability, multiple objectives, complex cost functions, and alternate solution approaches with their potential for solving practical problems. It is suggested that cost-based interactive heuristics coupled with graphical presentation of solutions may be the right method to deal with the more complex practical problems. Some basic generic heuristics are suggested and important software design and acquisition considerations are presented.     

Iterated local search for workforce scheduling and routing problems

The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times.     

Quantifying the benefits of route reoptimisation under stochastic customer demands

Incorporating route reoptimisation in the management of vehicle routing operations under stochastic demands yields benefits such as lower transportation and inventory costs. Because an investment in advanced information systems is indispensable for route reoptimisation, a firm needs to estimate the likely magnitude of these benefits before making an investment decision. This study addresses this information needed by providing a framework to assess the benefits more completely than previous studies. The framework, which is the key contribution of the research, comprises a set of tractable models that together address the costs of both inventory and transportation. By accounting for key determinants of route reoptimisation's benefits, including, for example, the volatility of customer demands, the models are applicable to a broad range of vehicle routing scenarios.     

Optimising cargo loading and ship scheduling in tidal areas

This paper describes a framework that combines decision theory and stochastic optimisation techniques to address tide routing (i.e. optimisation of cargo loading and ship scheduling decisions in tidal ports and shallow seas). Unlike weather routing, tidal routing has been little investigated so far, especially from the perspective of risk analysis. Considering the journey of a bulk carrier between N ports, a shipping decision model is designed to compute cargo loading and scheduling decisions, given the time series of the sea level point forecasts in these ports. Two procedures based on particle swarm optimisation and Monte Carlo simulations are used to solve the shipping net benefit constrained optimisation problem. The outputs of probabilistic risk minimisation are compared with those of net benefit maximisation, the latter including the possibility of a ‘rule-of-the-thumb’ safety margin. Distributional robustness is discussed as well, with respect to the modelling of sea level residuals. Our technique is assessed on two realistic case studies in British ports. Results show that the decision taking into account the stochastic dimension of sea levels is not only robust in real port and weather conditions, but also closer to optimality than standard practices using a fixed safety margin. Furthermore, it is shown that the proposed technique remains more interesting when sea level variations are artificially increased beyond the extremes of the current residual models.     

A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.     

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.      

Scheduling 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. These arise in the dial-a-ride problem, speed optimization in routing problems, the pollution-routing problem, long-haul vehicle routing and scheduling with working hour rules, and synchronization in arc routing.     

考虑路径冲突的AGV配置与调度优化

合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。     

Maritime crude oil transportation - A split pickup and split delivery problem

The maritime oil tanker routing and scheduling problem is known to the literature since before 1950. In the presented problem, oil tankers transport crude oil from supply points to demand locations around the globe. The objective is to find ship routes, load sizes, as well as port arrival and departure times, in a way that minimizes transportation costs. We introduce a path flow model where paths are ship routes. Continuous variables distribute the cargo between the different routes. Multiple products are transported by a heterogeneous fleet of tankers. Pickup and delivery requirements are not paired to cargos beforehand and arbitrary split of amounts is allowed. Small realistic test instances can be solved with route pre-generation for this model. The results indicate possible simplifications and stimulate further research.     

ARMMS: Analogical reasoning model management system for multicriteria vehicle scheduling

The transportation industry problem of scheduling vehicles combines the spatial characteristics of routing with time domain considerations of activity schedules. The problem is complex because of the numerous interacting constraints in the spatial and time domains. Further, some of the constraints are flexible and some arise in real-time. The scheduling problem is often presented with multiple objectives that are not all economic in nature and which can be contradictory to one another. In response to these needs, this paper describes an analogical reasoning model management system, called ARMMS, designed in the domain of vehicle scheduling. ARMMS consists of knowledge bases and data bases, a truth maintenance system, a user interface, an inference engine, a learning mechanism, and a model library. Given a scheduling problem, ARMMS searches its memory for solutions. If no solution is available, ARMMS falls back on an analogical problem solving approach in which similar experience can be recalled, and solutions to new, but similar, problems can be constructed. If no similar experience exists, ARMMS intelligently selects an appropriate algorithmic model from its model library, based on the input parameters and problem type, to solve the given problem. By combining experts' knowledge, analogical problem-solving approaches, and algorithmic methods, ARMMS provides an efficient problem-solving approach for vehicle scheduling and routing. ARMMS is also a feasible base for the development of intelligent model management systems.     

A multilevel machine and vehicle scheduling in a flexible manufacturing system

The paper presents a multilevel decision model for simultaneous machine and vehicle scheduling in a flexible manufacturing system. The system is composed of various machine types and a set of automated guided vehicles that permit each part to move between any pair of machines. The upper level of the decision model involves machine loading and part routing for which a bicriterion integer formulation is presented with the objective of balancing machine workloads and intermachine flows of parts. The lower level involves simultaneous scheduling of machines and vehicles for which a period-by-period heuristic is proposed based on a family of complex dispatching rules. The scheduling objective is to meet all part type requirements in a minimum time. Computational examples are included to illustrate the approach proposed.     

The vehicle routing and scheduling problem with cross-docking for perishable products under uncertainty: Two robust bi-objective models

This paper presents a bi-objective MILP model for the vehicle routing and scheduling problem with cross-docking for perishable products. It is demonstrated that considering merely one objective sacrifices the other one and that the L₁ metric method makes a suitable trade-off. Two robust models are developed when the travel time of the outbound vehicles and the freshness-life of the products are uncertain. The results show that the effect of the appearing uncertainty in the travel time on the deterioration of the objectives is higher than the effect of the freshness-life of the products, and using the proposed model, the freshness of the delivered products increases by 74.14% on average without increasing the distribution cost, which can decrease the waste.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。