A new solution for a dynamic cell formation problem with alternative routing and machine costs using simulated annealing

This paper presents an integer-linear programming approach for a cell formation problem (CFP) in a dynamic environment with a multi-period planning horizon. The objectives are to minimize the inter-cell movement and machine costs simultaneously. In dynamic environments, the product mix and demand are different but deterministic in each period. As a consequence, the formed cells in the current period may not be optimal for the next period. Thus, the reconfiguration of cells is required. Reconfiguration consists of re-forming part families, machine groups, and machine relocation. The CFP belongs to the category of NP-hard problems, thus we develop an efficient simulated annealing (SA) method to solve such a problem. The proposed mathematical model is optimally solved and the associated results are compared with the results obtained by the SA run. The results show that the gap between optimal and SA solutions is less than 4%, which indicates the efficiency of the developed SA scheme.     

On a bottleneck routing problem

An extremal routing problem with a criterion that has the sense of the largest edge length of a polygonal line is considered. It is assumed that the costs at every step (stage) of the travel may depend on a list of tasks that have not been fulfilled by the beginning of this step. In addition, there are constraints in the form of precedence conditions. An economical variant of the procedure is constructed based on the dynamic programming method.     

Multipolar routing: where dynamic and static routing meet

Assuming that the traffic matrix belongs to a polytope, we describe a new routing paradigm where each traffic matrix is routed a combination of a number of extreme routings. This combination depends on the current traffic matrix. Multipolar routing can be seen as a generalization of both routing and robust static routing. Moreover, the time complexity of multipolar routing is under control since it depends on the number of poles (i.e. the number of extreme routings) which can be defined by the network planner     

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.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.     

Hierarchical routing over dynamic wireless networks

The topology of a mobile wireless network changes over time. Maintaining routes between all nodes requires the continuous transmission of control information, which consumes precious power and bandwidth resources. Many routing protocols have been developed, trading off control overhead and route quality. In this paper, we ask whether there exist low‐overhead schemes that produce low‐stretch routes, even in large networks where all the nodes are mobile. We present a scheme that maintains a hierarchical structure within which constant‐stretch routes can be efficiently computed between every pair of nodes. The scheme rebuilds each level of the hierarchy periodically, at a rate that decreases exponentially with the level of the hierarchy. We prove that this scheme achieves constant stretch under a mild smoothness condition on the nodal mobility processes. Furthermore, we prove tight bounds for the network‐wide control overhead under the additional assumption of the connectivity graph forming a doubling metric space. Specifically, we show that for a connectivity model combining the random geometric graph with obstacles, constant‐stretch routes can be maintained with a total overhead of bits of control information per time unit. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 669–709, 2015     

Competitive analysis of a dispatch policy for a dynamic multi-period routing problem

We analyze an on-line algorithm (dispatch policy) for a dynamic multi-period routing problem. The objective is to minimize the total cost over all periods. We show that the competitive ratio of this policy for instances with customers located on the non-negative real line is .     

Global solution of bi-dimensional stochastic equation for a viscous gas

Received June 1998 – Revised October 1998     

On design of a survivable network architecture for dynamic routing: Optimal solution strategy and an efficient heuristic

We investigate network planning and design under volatile conditions of link failures and traffic overload. Our model is a non-simultaneous multi-commodity problem, with any particular two link failure being considered as one scenario. We show that the optimal solution model is not practically solvable for real-world problems and hence an efficient heuristic is provided which is O(n⁶) faster than the optimal model and is based on synthesizing a modified maximum spanning tree using an algorithm due to Gomory and Hu. The output of this procedure is then used to solve a much smaller linear program. Simulation results indicate that the heuristic is near optimal for problems with up to 40 nodes.     

Convexity and characterization of optimal policies in a dynamic routing problem

An infinite horizon, expected average cost, dynamic routing problem is formulated for a simple failure-prone queueing system, modelled as a continuous time, continuous state controlled stochastic process. We prove that the optimal average cost is independent of the initial state and that the cost-to-go functions of dynamic programming are convex. These results, together with a set of optimality conditions, lead to the conclusion that optimal policies are switching policies, characterized by a set of switching curves (or regions), each curve corresponding to a particular state of the nodes (servers).     

Comparison of policies in dynamic routing problems

We consider a company that has to satisfy customers' pick-up requests arriving over time every day. The overall objective of the company is to serve as many requests as possible at a minimum operational cost. When organizing its business the company has to fix some features of the service that may affect both service quality and operational costs. Some of these features concern the time a request is taken into account to plan its service, the associated deadline and the way requests are managed when the system is overloaded. In this paper we analyse several policies that can be implemented by the management of a carrier company in a multi-period context. For example, a company might reject all the requests that cannot be feasibly scheduled or accept all the requests and rely on a backup service in order to serve requests that are difficult to handle. Another interesting issue considered in this paper is the impact of collaborative service where two or more carrier companies, with their own customers, decide to share customers in order to optimize the overall costs. We set up a general framework to allow comparison of alternative service policies. Extensive computational results evaluating the number of lost requests and the distance travelled provide interesting insights.     

Iteration method in a routing problem with internal losses

The problem of a sequential traversal of sets is considered, which is complicated by the necessity of fulfilling (internal) tasks on the sets as well as by constraints in the form of precedence conditions. It is assumed that the method of aggregating the expenses is additive. For the appearing extremal problem with dependent variables, an equivalent transformation to an optimization problem on a Cartesian product is proposed. Based on this, an iteration method is constructed that uses a reconstructible model of the courier problem (a traveling salesman problem complicated by precedence conditions).     

Congestion control using dynamic routing and flow control

In this paper, the congestion control in store and forward computer com-munication networks is studied, the method employed consists of a combination of a dynamic routing policy that minimizes the delay, and buffer nianagement schemes to control the flow of data. Simulation using liner programming has been carried out, under balanced and transient traffic conditions, on a simple 3–node network , the relative merits and drawbacks of each approach are discussed. Irland [2], showed that with static routing, the SQRT scheme improves the switch performance. In this paper it is shown that in the case of dynamic routing, the SQRT is an excellent solution to remedy the performance degradation caused by CP and CS schemes     

Network design and dynamic routing under queueing demand

Given a nonhierarchical network and time-varying flow requirements, the problem of determining optimal capacities is termed design; that of determining optimal flows as dynamic routing. We formulate a linear program to solve both simultaneously in the case of deterministic flow requirements. A probability distribution termed the Erlang Difference Distribution is derived from a queueing model to describe random flow requirements, and this case leads to a separable convex program that has a linear programming equivalent. Both linear programs are amenable to Dantzig-Wolfe decomposition, which reveals subproblems that yield to special techniques of solution.

---

Zusammenfassung Gegeben sei ein nicht hierarchisches Netzwerk mit zeitabhängigen Flüssen. Das Problem, optimale Kapazitäten festzusetzen, wird als Netzwerk-Entwurf bezeichnet. Die Bestimmung optimaler Flüsse bezeichnet man als dynamische Flußführung. Es wird ein lineares Programm formuliert, das beide Probleme gleichzeitig löst, sofern deterministische Flüsse vorliegen. Sodann wird eine Wahrscheinlichkeitsverteilung namens Erlang'sche Differenzen-Verteilung aus einem Warteschlangenmodell abgeleitet, um zufällige Flüsse zu beschreiben. Dies führt auf ein separables konvexes Programm mit einem linearen Programm als Äquivalent. Bei beiden betrachteten linearen Programmen kann die Dantzig-Wolfe Dekomposition angewendet werden, wobei die auftretenden Teilprobleme durch spezielle Techniken gelöst werden können.

---

---

Research partially supported by National Science Foundation Grant ECS-8300214.     

Optimizing garbage collection vehicle routing problem with alternative fuel-powered vehicles

Abstract

This paper considers the garbage collection problem in which vehicles with multiple compartments are used to collect the garbage. The vehicles are considered to be Alternative Fuel-powered Vehicles (AFVs). Compared with the traditional fossil fuel powered vehicles, the AFVs have limited fuel tank capacity. In addition, AFVs are allowed to refuel only at the depot. We provide a mathematical formulation and develop two solution approaches to solve the problem. The first approach is based on the saving algorithm, while the second is based on the ant colony system (ACS) metaheuristic. New problem instances have been generated to evaluate the performance of the proposed algorithms.     

The robust network loading problem with dynamic routing

In this paper the Robust Network Loading problem with splittable flows and dynamic routing under polyhedral uncertainty for the demands is considered. Polyhedral results for the capacity formulation of the problem are given. The first exact approach for solving the problem is presented. A branch-and-cut algorithm based on the proposed capacity formulation is developed. Computational results using the hose polyhedron to model the demand uncertainty are discussed.     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.