Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

Internet packet routing: Application of a K-quickest path algorithm

This paper describes a study on the application of an algorithm to rank the K-quickest paths to the routing of data packets in Internet networks. For this purpose an experimental framework was developed by considering two types of random generated networks. To simulate values of the IP packet sizes, a truncated Pareto distribution was defined, having in mind to reflect a key feature of Internet traffic, namely its self-similar stochastic nature. Results concerning the average CPU times of the algorithm for the different sets of experiments will be presented and discussed.     

A path relinking algorithm for a multi-depot periodic vehicle routing problem

In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency.     

A memetic algorithm for the virtual network mapping problem

The Internet has ossified. It has lost its capability to adapt as requirements change. A promising technique to solve this problem is the introduction of network virtualization. Instead of directly using a single physical network, working just well enough for a limited range of applications, multiple virtual networks are embedded on demand into the physical network, each of them perfectly adapted to a specific application class. The challenge lies in mapping the different virtual networks with all the resources they require into the available physical network, which is the core of the virtual network mapping problem. In this work, we introduce a memetic algorithm that significantly outperforms the previously best algorithms for this problem. We also offer an analysis of the influence of different problem representations and in particular the implementation of a uniform crossover for the grouping genetic algorithm that may also be interesting outside of the virtual network mapping domain. Furthermore, we study the influence of different hybridization techniques and the behaviour of the developed algorithm in an online setting.     

Simulating vehicular traffic in a network using dynamic routing

We present a new numerical code which solves the Lighthill – Whitham model, the classic macroscopic model for vehicular traffic flow, in a network with multi-destinations. We use a high-resolution shock-capturing scheme with approximate Riemann solver to solve the partial differential equations of the Lighthill – Whitham theory. These schemes are very efficient, robust and moreover well adapted to simulations of traffic flows. We develop a theory of dynamic routing including a procedure for traffic flow assignment at junctions which reproduces the correct propagation of irregularities and ensures at the same time conservation of the number of vehicles.     

Branch-and-price and constraint programming for solving a real-life technician dispatching problem

We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. A branch-and-price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with constraint programming in the column generation phase. The column generation takes advantage of the fact that each technician can satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice.     

A scheme for synchronizing clocks connected by a packet communication network

Consider a communication system in which a transmitter equipment sends fixed-size packets of data at a uniform rate to a receiver equipment. Consider also that these equipments are connected by a packet-switched network, which introduces a random delay to each packet. Here we propose an adaptive clock recovery scheme able of synchronizing the frequencies and the phases of these devices, within specified limits of precision. This scheme for achieving frequency and phase synchronization is based on measurements of the packet arrival times at the receiver, which are used to control the dynamics of a digital phase-locked loop. The scheme performance is evaluated via numerical simulations performed by using realistic parameter values.     

Well-posedness of a parametric traffic network problem

We define kinds of approximate solutions of a traffic network problem and obtain relations to approximate solutions of the corresponding quasivariational inequality. Using these results we establish sufficient conditions for the Tikhonov well-posedness in the sense of Levitin–Polyak of our traffic network problem.     

An analysis of parallel routing algorithm on hypercube network by employing covering problem and assignment problem

The application of Hadamard matrix to the parallel routings on the hypercube network was presented by Rabin. In this matrix, every two rows differ from each other by exactlyn/2 positions. A set ofn disjoint paths onn-dimensional hypercube network was designed using this peculiar property of Hadamard matrix. Then, the data is dispersed into n packets and these n packet are transmitted along thesen disjoint paths. In this paper, Rabin’s routing algorithm is analyzed in terms of covering problem and assignment problem. Finally, we conclude thatn packets dispersed are placed in well-distributed positions during transmission, and the randomly selected paths are almost a set ofn edge-disjoint paths with high probability.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem

This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results, they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms.     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the transportation networks of Madrid and Barcelona—show the effectiveness of the approach.     

System dynamics and feedback control problem formulations for real time dynamic traffic routing

This paper formulates the Dynamic Traffic Routing (DTR) problem as a real-time feedback control problem. Three different forms of the formulation are presented:

• 1.(1) distributed parameter system form derived from the conservation law;
• 2.(2) space discretized continuous lumped parameter form;
• 3.(3) space and time discretized lumped parameter form.

These formulations can be considered as the starting points for development of feedback control laws for the different control problems stated in this paper. This paper presents the feedback control problems, and does not discuss in detail the methodology of solution techniques which could be used to solve these problems. However, for the sake of completeness a brief treatment of the three forms are included in this paper to show possible ways to design the controllers.     

The routing open-shop problem on a network: Complexity and approximation

In the routing open-shop problem, jobs are located at nodes of an undirected transportation network, and the machines travel on the network to execute jobs in the open-shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a nonpreemptive schedule that minimizes the makespan. We prove that the problem is NP-hard even on a two-node network with two machines, and even on a two-node network with two jobs and m machines. We develop polynomial-time approximation heuristics and obtain bounds on their approximation performance.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

We study a selective and periodic inventory routing problem (SPIRP) and develop an Adaptive Large Neighborhood Search (ALNS) algorithm for its solution. The problem concerns a biodiesel production facility collecting used vegetable oil from sources, such as restaurants, catering companies and hotels that produce waste vegetable oil in considerable amounts. The facility reuses the collected waste oil as raw material to produce biodiesel. It has to meet certain raw material requirements either from daily collection, or from its inventory, or by purchasing virgin oil. SPIRP involves decisions about which of the present source nodes to include in the collection program, and which periodic (weekly) routing schedule to repeat over an infinite planning horizon. The objective is to minimize the total collection, inventory and purchasing costs while meeting the raw material requirements and operational constraints. A single-commodity flow-based mixed integer linear programming (MILP) model was proposed for this problem in an earlier study. The model was solved with 25 source nodes on a 7-day cyclic planning horizon. In order to tackle larger instances, we develop an ALNS algorithm that is based on a rich neighborhood structure with 11 distinct moves tailored to this problem. We demonstrate the performance of the ALNS, and compare it with the MILP model on test instances containing up to 100 source nodes.     

An exact algorithm for a single-vehicle routing problem with time windows and multiple routes

This paper describes an exact algorithm for solving a problem where the same vehicle performs several routes to serve a set of customers with time windows. The motivation comes from the home delivery of perishable goods, where vehicle routes are short and must be combined to form a working day. A method based on an elementary shortest path algorithm with resource constraints is proposed to solve this problem. The method is divided into two phases: in the first phase, all non-dominated feasible routes are generated; in the second phase, some routes are selected and sequenced to form the vehicle workday. Computational results are reported on Euclidean problems derived from benchmark instances of the classical vehicle routing problem with time windows.     

A sweep-based algorithm for the fleet size and mix vehicle routing problem

This paper presents a new sweep-based heuristic for the fleet size and mix vehicle routing problem. This problem involves two kinds of decisions: the selection of a mix of vehicles among the available vehicle types and the routing of the selected fleet. The proposed algorithm first generates a large number of routes that are serviced by one or two vehicles. The selection of routes and vehicles to be used is then made by solving to optimality, in polynomial time, a set-partitioning problem having a special structure. Results on a set of benchmark test problems show that the proposed heuristic produces excellent solutions in short computing times. Having a fast but good solution method is needed for transportation companies that rent a significant part of their fleet and consequently can take advantage of frequent changes in fleet composition. Finally, the proposed heuristic produced new best-known solutions for three of the test problems; these solutions are reported.     

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.