Adaptation of some vehicle fleet mix heuristics

Standard models used for the combined vehicle routing and vehicle fleet composition problem use the same value for the unit running cost across vehicles. In practice such a parameter depends on several factors and particularly on the capacity of the vehicle. The purpose of this paper is to show simple modifications of some well known methods to allow for variable running costs; and also to assess the effect of neglecting such variability. Interesting numerical results, measured in terms of changes in total cost or/and fleet configuration, are found at no extra computational effort.     

An investigation into the vehicle routing problem with time windows and link capacity constraints

In this work, we investigate a new, yet practical, variant of the vehicle routing problem called the vehicle routing problem with time windows and link capacity constraints (VRPTWLC). The problem considers new constraints imposed on road links with regard to vehicle passing tonnage, which is motivated by a business project with a Hong Kong transportation company that transports hazardous materials (hazmats) across the city and between Hong Kong and mainland China. In order to solve this computationally challenging problem, we develop a tabu search heuristic with an adaptive penalty mechanism (TSAP) to help manage the company's vehicle fleet. A new data set and its generation scheme are also presented to help validate our solutions. Extensive computational experiments are conducted, showing the effectiveness of the proposed solution approach.     

Mixed-fleet single-terminal bus scheduling problem: Modelling,solution scheme and potential applications

Reducing pollutant emissions and promoting sustainable mobility solutions, including Public Transport (PT), are increasingly becoming key objectives for policymakers worldwide. In this work we develop an optimal vehicle scheduling approach for next generation PT systems, considering the instance of mixed electric / hybrid fleet. Our objective is that of investigating to what extent electrification, coupled with optimal fleet management, can yield operational cost savings for PT operators. We propose a Mixed Integer Linear Program (MILP) to address the problem of optimal scheduling of a mixed fleet of electric and hybrid / non-electric buses, coupled with an ad-hoc decomposition scheme aimed at enhancing the scalability of the proposed MILP. Two case studies arising from the PT network of the city of Luxembourg are employed in order to validate the model; sensitivity analysis to fleet design parameters is performed, specifically in terms of fleet size and fleet composition. Conclusions point to the fact that careful modelling and handling of mixed-fleet conditions are necessary to achieve operational savings, and that marginal savings gradually reduce as more conventional buses are replaced by their electric counterparts. We believe the methodology proposed may be a key part of advanced decision support systems for policymakers and operators that are dealing with the on-going transition from conventional bus fleets towards greener transport solutions.     

Network Models for Fleet Management*

This paper presents network models to determine the optimal replacement policy for a fleet of vehicles over a finite planning horizon. First, a minimum cost-flow model is developed to determine the optimal replacement schedule for a fleet of fixed size consisting of a single type of vehicle of various ages. The model is then extended to allow for restrictions on capital expenditures that limit the purchase of new vehicles in any time period and to allow for fluctuations in the fleet size due to planned expansion or retrenchment. Finally, a multi-commodity network model is developed for a fleet consisting of multiple vehicle types and ages.     

Multi-depot vehicle routing problem with time windows under shared depot resources

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.     

The planning of cycle trips in the province of East Flanders

Traditional route planners assist in finding the shortest or fastest route from one place to another. This paper presents a novel approach to path finding in a directed graph, namely a target distance, motivated by the problem that a recreational cyclist deals with when searching a nice route of a certain length. The problem is defined as a variant of the arc orienteering problem (AOP), a new combinatorial optimisation problem in which the score of a route in a directed graph has to be maximised by visiting arcs, while each arc can be visited at most once and the total cost of the route should not exceed a predefined cost. The contribution of this paper is threefold: (1) a mathematical model of the AOP is provided, (2) a metaheuristic method that solves AOP instances to near optimality in 1 s of execution time, is proposed and evaluated, and (3) two real-life applications of the method are presented. An on-line cycle route planning application offers personalised cycle routes based on user preferences, and an SMS service provides cyclists “in the field” with routes on demand.     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.     

A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia

We introduce, model and solve to optimality a rich multi-product, multi-period and multi-compartment vehicle routing problem with a required compartment cleaning activity. This real-life application arises in the olive oil collection process in Tunisia, where regional collection offices dispose of a fleet of vehicles to collect one or several grades of olive oil from a set of producers. For each grade, the quantity offered by a producer changes dynamically over the planning horizon. We first provide a mathematical formulation of the problem, along with a set of known and new valid inequalities. We then propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios to demonstrate to our industrial partner the advantages of using multi-compartment vehicles.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

The maximum flow problem with disjunctive constraints

We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly $\mathcal{NP}$ -hard, even if the conflict graph consists only of unconnected edges. This result still holds if the network consists only of disjoint paths of length three. For forcing graphs we also provide a sharp line between polynomially solvable and strongly $\mathcal{NP}$ -hard instances for the case where the flow values are required to be integral. Moreover, our hardness results imply that no polynomial time approximation algorithm can exist for both problems. In contrast to this we show that the maximum flow problem with a forcing graph can be solved efficiently if fractional flow values are allowed.     

Fleet and revenue management in car rental companies: A literature review and an integrated conceptual framework

This paper aims to present, define and structure the car rental fleet management problem, which includes operational fleet management issues and problems traditionally studied under the revenue management framework. The car rental business has challenging and distinctive characteristics, which are mainly related with fleet and decision-making flexibility, and that render this problem relevant for academic research and practical applications. Three main contributions are presented: an in-depth literature review and discussion on car rental fleet and revenue management issues, a novel integrating conceptual framework for this problem, and the identification of research directions for the future development of the field.     

Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements

Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists in finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. A real-life case study taken from the cash supply chain in the Netherlands highlights the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For instances of real-life problems, we distinguish between coin and banknote distribution, as vehicle capacities only matter when considering the former. Finally, we report on the effectiveness of the valid inequalities in closing the optimality gap at the root node for both the synthetic and the real-life instances and conclude with a sensitivity analysis on the most significant input parameters of our model.     

MODEL FORMULATION FOR FLEET SIZE ANALYSIS OF A UNIVERSITY MOTOR POOL

A GPSS/360 model was developed to investigate the behavior of a university's motor pool dispatch fleet. Time-series data were collected and frequency distributions were constructed for vehicle request patterns and trip-duration times. Regression analysis was performed to formulate trip mileage generators as functions of service time. Appropriate statistical goodness-of-fit tests were conducted to ascertain the extent of congruence between actual system behavior and expectations based on a number of theoretical distributions. Analysis of simulated response variables indicates that the model's internal structure reproduces reality to a high degree. Fifteen years of simulated experience were generated for six alternative fleet size configurations; results suggest that reductions in existing fleet capacity could be realized without effecting undue impairment in service levels.     

The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

Augmenting weighted graphs to establish directed point-to-point connectivity

We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices \(P=\left\{ {\left( {s_1 ,t_1 } \right) ,\ldots ,\left( {s_p ,t_p } \right) } \right\} \), one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present some parameterized algorithms and parameterized complexity results for it.     

Experience with a multi-year fleet planning model

The fleet planning problem requires determination of the changing airline fleet mix based on existing traffic levels and projected growth, on the existing fleet, various aircraft types available in the future, and other operational and financial considerations. Several applicable mathematical formulations have been reported. One of these has been programmed for the computer and used by the authors for several years. This paper discusses the application of that model to real airline planning situations. Such practical experience has effected changes in the program and the manner it is used in fleet planning studies.     

Perfect Circular Arc Coloring

The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n² m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.Partially supported by Project 02139 of Education Ministry of China.Supported in part by the Research Grants Council of Hong Kong (Project No. HKU7054/03P) and a seed funding for basic research of HKU.     

Computing monotone disjoint paths on polytopes

The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph consisting of the set of vertices and arcs of a polytope P directed by a linear objective function in general position. The study of paths on polytopal digraphs stems from a long standing problem, that of designing a polynomial-time pivot method, or proving none exists. To study disjoint paths it would be useful to have a tool to compute them. Without explicitly computing the digraph we develop an algorithm to compute a maximum cardinality set of source to sink paths in a polytope, even in the presence of degeneracy. The algorithm uses a combination of networks flows, the simplex method, and reverse search. An implementation is available.     

A novel approach to subgraph selection with multiple weights on arcs

In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs for routing the flow. The problem is tractable when a single weight is given on each arc. However, in many real-world applications, several weights are needed to describe the features of arcs, including transit cost, arrival time, delay, profit, security, reliability, deterioration, and safety. In this case, finding an optimal solution becomes difficult. We propose a heuristic algorithm for this purpose. First, we compute the relative efficiency of the arcs by using data envelopment analysis techniques. We then determine a subgraph with efficient arcs using a linear programming model, where the objective function is based on the relative efficiency of the arcs. The flow obtained satisfies the arc capacity constraints and the integrality property. Our proposed algorithm has polynomial runtime and is evaluated in rigorous experiments.