District design for arc-routing applications

In this paper we address the problem of district design for the organisation of arc-routing activities. In particular, the focus is on operations like winter gritting and road maintenance. The problem involves how to allocate the road network edges to a set of depots with given locations. The collection of edges assigned to a facility forms a district in which routes have to be designed that start and end at the facility. Apart from the ability to support good arc routing, well-designed districts for road-maintenance operations should have the road network to be serviced connected and should define clear geographical boundaries. We present three districting heuristics and evaluate the quality of the partitions by solving capacitated arc routing problems in the districts, and by comparing the solution values with a multi-depot CARP cutting plane lower bound. Our experiments reveal that based on global information about the distribution system (ie the number of facilities or districts, the average edge demand and the vehicle capacity) and by using simple guidelines, an adequate districting policy may be selected.     

GIS technology as an environment for testing an advanced mathematical model for optimization of road maintenance

In the paper, we consider a Chinese postman problem and show how integration of an advanced mathematical model with GIS technology can be beneficial providing a powerful tool for developing, testing and applying sophisticated heuristics for arc routing problems. We give details of an implementation of several recently developed heuristics for the Chinese postman problem with priority nodes that are integrated with GIS software. In the end, we show how a GIS visualization can be helpful in finding and presenting the results.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

Bandwidth packing with priority classes

The bandwidth packing problem is defined as the selection and routing of messages from a given list of messages with prespecified requirements on demand for bandwidth. The messages have to be routed over a network with given topology so that the generated revenue is maximized. Messages to be routed are classified into two priority classes. An integer programming based formulation of this problem is proposed and a Lagrangean relaxation based methodology is described for solving this problem. A general purpose heuristic is then developed for generating feasible solutions of good quality. Several numerical experiments are conducted using a number of problem parameters such as number of messages, ratio of messages for lower and higher priority classes, capacity of links, and demand distribution of messages belonging to different classes and high quality solutions to the priority bandwidth packing problem are generated under the different situations.     

Models for a Steiner multi-ring network design problem with revenues

The Steiner multi-ring network design problem with revenues consists of designing node-disjoint multiple rings connected by a specific node (hub) and passing through all the nodes with high priority of service and some of the nodes with low priority of service. The number of nodes in each ring has an upper bound to assure a certain level of service. Besides the usual arc link costs, we also consider revenues between each pair of nodes in the same ring, even when they are not connected by a direct link. The objective is to minimize the difference between the total connection cost and total revenue. The problem is a generalization of the problem studied in Gouveia and Pires (Eur J Oper Res 133:21–31, 2001a) and it can also be seen as a combination of variants of two NP-Hard problems, the vehicle routing problem and the maximum edge-weighted clique problem. We introduce and discuss two types of integer linear programming formulations and propose some valid inequalities to strengthen the linear programming relaxation. Computational results are presented to evaluate the quality of the linear programming relaxation bounds associated with these formulations as well as efficiency of the models to obtain the optimal integer solutions.     

A post-optimization method for the routing and wavelength assignment problem applied to scheduled lightpath demands

We consider here a NP-hard problem related to the Routing and Wavelength Assignment (RWA) problem in optical networks, dealing with Scheduled Lightpath Demands (SLDs). An SLD is a connection demand between two nodes of the network, during a certain time. Given a set of SLDs, we want to assign a lightpath, i.e. a routing path and a wavelength, to each SLD, so that the total number of required wavelengths is minimized. The constraints are the following: a same wavelength must be assigned all along the edges of the routing path of any SLD; at any time, a given wavelength on a given edge of the network cannot be used to satisfy more than one SLD. To solve this problem, we design a post-optimization method improving the solutions provided by a heuristic. The experimental results show that this post-optimization method is quite efficient to reduce the number of necessary wavelengths.     

Survivable network design with shared-protection routing

In this paper we study the problem of designing a survivable telecommunication network with shared-protection routing. We develop a heuristic algorithm to solve this problem. Recent results in the area of global re-routing have been used to obtain very tight lower bounds for the problem. Our results indicate that in a majority of problem instances, the average gap between the heuristic solutions and the lower bounds is within 5%. Computational experience is reported on randomly generated problem instances with up to 35 nodes, 80 edges and 595 demand pairs and also on the instances available in SNDlib database.     

Improved load balancing and resource utilization for the Skill Vehicle Routing Problem

The Skill Vehicle Routing Problem (Skill VRP) considers vehicle routing under the assumption of skill requirements given on demand nodes. These requirements have to be met by the serving vehicles. No further constraints, like capacity or cost restrictions, are imposed. Skill VRP solutions may show a tendency to have a bad load balancing and resource utilization. In a majority of solutions only a subset of vehicles is active. Moreover, a considerable share of demand nodes is served by vehicles that have a skill higher than necessary. A reason for that solution behavior lies in the model itself. As no resource restrictions are imposed, the Skill VRP tends to produce TSP-like solutions. To obtain better balanced solutions, we introduce two new approaches. First we propose a minmax model that aims at minimizing the maximal vehicle tour length. Second we suggest a two-step method combining the minmax approach with a distance constrained model. Our experiments illustrate that these approaches lead to improvements in load balancing and resource utilization, but, with different impact on routing costs.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. 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. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

On the Hierarchical Chinese Postman Problem with linear ordered classes

The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn⁴) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity.     

Minimizing waiting times in a route design problem with multiple use of a single vehicle

In this study we introduce a routing problem with multiple use of a single vehicle and service time in demand points (clients) with the aim of minimizing the sum of clients waiting time to receive service. This problem is relevant in the distribution of aid, in disaster stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints which force multiple use of the vehicle in the planning horizon. This paper presents and compares two mixed integer formulations for this problem, based on a multi–level network.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

Open vehicle routing problem with driver nodes and time deadlines

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time.     

The bottleneck transportation problem with auxiliary resources

In this paper, we introduce a new extension of the bottleneck transportation problem where additionally auxiliary resources are needed to support the transports. A single commodity has to be sent from supply to demand nodes such that the total demand is satisfied and the time at which all units of the commodity have arrived at the demand nodes is minimized. We show that already the problem with a single demand node and a single auxiliary resource is NP-hard and consider some polynomially solvable special cases.     

Optimizing Bernoulli Routing Policies for Balancing Loads on Call Centers and Minimizing Transmission Costs

We address the problem of assigning probabilities at discrete time instants for routing toll-free calls to a given set of call centers to minimize a weighted sum of transmission costs and load variability at the call centers during the next time interval.We model the problem as a tripartite graph and decompose the finding of an optimal probability assignment in the graph into the following problems: (i) estimating the true arrival rates at the nodes for the last time period; (ii) computing routing probabilities assuming that the estimates are correct. We use a simple approach for arrival rate estimation and solve the routing probability assignment by formulating it as a convex quadratic program and using the affine scaling algorithm to obtain an optimal solution.We further address a practical variant of the problem that involves changing routing probabilities associated with k nodes in the graph, where k is a prespecified number, to minimize the objective function. This involves deciding which k nodes to select for changing probabilities and determining the optimal value of the probabilities. We solve this problem using a heuristic that ranks all subsets of k nodes using gradient information around a given probability assignment.The routing model and the heuristic are evaluated for speed of computation of optimal probabilities and load balancing performance using a Monte Carlo simulation. Empirical results for load balancing are presented for a tripartite graph with 99 nodes and 17 call center gates.     

Emergency Logistics Planning in Natural Disasters

Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas as soon as possible so that relief operations are accelerated. In this study, a planning model that is to be integrated into a natural disaster logistics Decision Support System is developed. The model addresses the dynamic time-dependent transportation problem that needs to be solved repetitively at given time intervals during ongoing aid delivery. The model regenerates plans incorporating new requests for aid materials, new supplies and transportation means that become available during the current planning time horizon. The plan indicates the optimal mixed pick up and delivery schedules for vehicles within the considered planning time horizon as well as the optimal quantities and types of loads picked up and delivered on these routes. In emergency logistics context, supply is available in limited quantities at the current time period and on specified future dates. Commodity demand is known with certainty at the current date, but can be forecasted for future dates. Unlike commercial environments, vehicles do not have to return to depots, because the next time the plan is re-generated, a node receiving commodities may become a depot or a former depot may have no supplies at all. As a result, there are no closed loop tours, and vehicles wait at their last stop until they receive the next order from the logistics coordination centre. Hence, dispatch orders for vehicles consist of sets of “broken” routes that are generated in response to time-dependent supply/demand. The mathematical model describes a setting that is considerably different than the conventional vehicle routing problem. In fact, the problem is a hybrid that integrates the multi-commodity network flow problem and the vehicle routing problem. In this setting, vehicles are also treated as commodities. The model is readily decomposed into two multi-commodity network flow problems, the first one being linear (for conventional commodities) and the second integer (for vehicle flows). In the solution approach, these sub-models are coupled with relaxed arc capacity constraints using Lagrangean relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size.     

Hybrid heuristics for a short sea inventory routing problem

We consider a short sea fuel oil distribution problem where an oil company is responsible for the routing and scheduling of ships between ports such that the demand for various fuel oil products is satisfied during the planning horizon. The inventory management has to be considered at the demand side only, and the consumption rates are given and assumed to be constant within the planning horizon. The objective is to determine distribution policies that minimize the routing and operating costs, while the inventory levels are maintained within their limits. We propose an arc-load flow formulation for the problem which is tightened with valid inequalities. In order to obtain good feasible solutions for planning horizons of several months, we compare different hybridization strategies. Computational results are reported for real small-size instances.     

Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns

We study the routing of a single vehicle that delivers multiple products under stochastic demand. Specifically, we investigate two practical variations of this problem: (i) The case in which each product type is stored in its dedicated compartment in the vehicle, and (ii) the case in which all products are stored together in the vehicle’s single compartment. Suitable dynamic programming algorithms are proposed to determine the minimum expected (routing) cost for each case. Furthermore, the optimal routing policy is derived by developing appropriate theorems. The efficiency of the algorithms is studied by solving large problem sets.     

Routing of platforms in a maritime surface surveillance operation

Maritime surface surveillance is the process of obtaining and maintaining information about surface ships in a certain sea area. It is carried out by maritime platforms such as frigates, helicopters or maritime patrol aircraft. Surface surveillance plays a vital role in maritime operations like trade embargo operations, counterdrug operations and traditional warfare operations.The problem of finding optimal tactics for a single surveillance unit is a routing problem which can to some extent be considered as an extension of the on-line travelling salesman problem, but there are essential complications which call for a different approach. A mathematical formulation of the surveillance routing problem is given in this paper. The complications of this problem, in comparison to the on-line travelling salesman problem, are explained.This routing problem is part of the rather complicated process of maritime surface surveillance. SURPASS, an acronym of SURface Picture ASSessment, is a computer model which simulates this process. The model SURPASS provides insight into both the means (i.e. platforms and sensors) needed for a surveillance operation and the effectiveness of various existing and newly developed rules for surveillance tactics. The structure of SURPASS is explained, including the way in which it solves the surveillance routing problem. A number of decision rules that can be used in the routing of the surveillance units are described. The effectiveness of these rules is analysed and evaluated.