Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.     

A note on relatives to the Held and Karp 1-tree problem

We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.     

Dynamic material handling for a class of flexible manufacturing systems

A real-time hierarchical routing control scheme for a large class of material handling systems is presented. The higher level (coordinator) performs resource allocation tasks and supplies parameter values to the lower (local control) level. The lower level operates in an autonomous (without continuous supervision) and distributed fashion. If state information is made available to the coordinator, the routing strategy can furthermore be adaptively adjusted.     

On the waiting time of arriving aircrafts and the capacity of airports with one or two runways

In this paper we examine a model for the landing procedure of aircrafts at an airport. The characteristic feature here is that due to air turbulence the safety distance between two landing aircrafts depends on the types of these two machines. Hence, an efficient routing of the aircraft to two runways may reduce their waiting time.     

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.      

Routing in Queues with Delayed Information

We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.     

An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem

In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation.     

An algorithm for network dimensioning under reliability considerations

In this paper we introduce a new methodology to adjust link capacities in circuit switched networks taking into account the costing policy and reliability considerations. This methodology, which is an extension of previous work on reliability evaluation using routing models, is based on a cyclic decomposition algorithm which alternates between a routing subproblem and a link capacity adjustment subproblem. The proposed procedure, which is shown to converge to a global optimum for the dimensioning/routing problem, has been tested on a 14 undirected arc problem for various levels of link failure probability. The numerical results are extremely satisfactory and they demonstrate the usefulness of the proposed method for proper network dimensioning.     

The effect of delayed feedback information on network performance

The performance of a network subject to either state dependent or state independent flow control is investigated. In the state dependent case, the flow control policy is a function of the total number of packets for which the controller has not yet received an acknowledgment. In this case it is shown that the optimal flow control is a sliding window mechanism. The effect of the delayed feedback on the network performance as well as the size of the window are studied. The state independent optimal rate is also derived. The performance of the state dependent and state independent flow control policies are compared. Conditions for employing one of the two types of flow control policies for superior end-to-end network performance are discussed. All the results obtained are demonstrated using simple examples.