Algorithms for the non-bifurcated network design problem

In this paper we consider the non-bifurcated network design problem where a given set of cities must be connected by installing on a given set of links integer multiples of some base capacity so that a set of commodity demands can be routed. Each commodity flow is constrained to run through a single path along the network. The objective is to minimize the sum of capacity installation and routing costs. We present an exact algorithm and four new heuristics. The first heuristic generates an initial feasible solution, then it improves it until a necessary condition for optimality is satisfied. Two heuristics are partial enumeration methods and the last one iteratively applies a tabu search method to different initial feasible solutions. Computational results over a set of test problems from the literature show the effectiveness of the proposed algorithms.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Inventory control under speculation: Myopic heuristics and exact procedures

We consider a periodic review inventory problem in which the purchasing cost exhibits a noticeable increase (deterministic or stochastic) in the second period and remains at the higher value for the remainder of the problem. (This simplification clarifies the nature of the myopic heuristic, but is not necessary for use of the heuristic in practice.) This results in a strategy that holds inventories due to speculation. We develop solution procedures to find the optimal inventory levels for both stationary and non-stationary demands. We establish that the problem with stochastic speculation behaves exactly like a problem with deterministic speculation with the same mean increase in price. We propose, based on the case of deterministic demands, simple myopic heuristics and study their effectiveness. We observe that these heuristics perform very well for exponential demands. However, for the case of uniform demands these heuristics are most effective when the increase in price is large compared to the holding cost.     

A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms

This paper introduces a pickup and delivery problem encountered in servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. This paper describes several construction heuristics as well as a tabu search algorithm. Computational results are presented.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

Synchronized routing of seasonal products through a production/distribution network

This paper presents a multi-period vehicle routing problem for a large-scale production and distribution network. The vehicles must be routed in such a way as to minimize travel and inventory costs over a multi-period horizon, while also taking retailer demands and the availability of products at a central production facility into account. The network is composed of one distribution center and hundreds of retailers. Each retailer has its demand schedule representing the total number of units of a given product that should have been received on a given day. Many high value products are distributed. Product availability is determined by the production facility, whose production schedule determines how many units of each product must be available on a given day. To distribute these products, the routes of a heterogeneous fleet must be determined for a multiple period horizon. The objective of our research is to minimize the cost of distributing products to the retailers and the cost of maintaining inventory at the facility. In addition to considering product availability, the routing schedule must respect many constraints, such as capacity restrictions on the routes and the possibility of multiple vehicle trips over the time horizon. In the situation studied, no more than 20 product units could be carried by a single vehicle, which generally limited the number of retailers that could be supplied to one or two per route. This article proposes a mathematical formulation, as well as some heuristics, for solving this single-retailer-route vehicle routing problem. Extensions are then proposed to deal with the multiple-retailer-route situation.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

An exact algorithm for a cross-docking supply chain network design problem

This paper proposes a branch-and-price algorithm as an exact algorithm for the cross-docking supply chain network design problem introduced by one of the authors of this paper. The objective is to optimally locate cross-docking (CD) centres and allocate vehicles for direct transportation services from the associated origin node to the associated CD centre or from the associated CD centre to the associated destination node so as to satisfy a given set of freight demands at minimum cost subject to the associated service (delivery) time restriction. A set-partitioning-based formulation is derived for the problem for which some solution properties are characterized. Based on the properties, a branch-and-price algorithm is derived. The properties can also be used in deriving any efficient local search heuristics with the move operation (neighbourhood search operation) of modifying assignment of some freight demands from current CD centres to other CD centres. Computational experiments show that the branch-and-price algorithm is effective and efficient and also that the solution properties contribute to improve the efficiency of the local search heuristics.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.     

Production planning and warehouse management in supply networks with inter-facility mold transfers

This paper, considers with the problem of production capacity and warehouse management in a supply network in which inter-plant mold transfers are enabled. The supply network has a limited number of very expensive molds which can be transferred from a plant to another making it possible for each plant to produce the entire product gamut. It is assumed that warehouses in this supply network can be activated and deactivated as required, and that material transfers from a warehouse to another are also possible. The objective is to develop a capacity and warehouse management plan that satisfies the expected market demands with the lowest possible cost. A mixed integer programming model for the problem is suggested and its properties are discussed. A linear programming-based heuristic that combines Lagrangian relaxation and linear programming duality to generate lower and upper bounds for the problem is proposed. Finally, based on a designed experiment the performance of the heuristic on a set of generated test problems is reported and discussed.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

A scatter search heuristic for the capacitated clustering problem

This paper proposes a scatter search-based heuristic approach to the capacitated clustering problem. In this problem, a given set of customers with known demands must be partitioned into p distinct clusters. Each cluster is specified by a customer acting as a cluster center for this cluster. The objective is to minimize the sum of distances from all cluster centers to all other customers in their cluster, such that a given capacity limit of the cluster is not exceeded and that every customer is assigned to exactly one cluster. Computational results on a set of instances from the literature indicate that the heuristic is among the best heuristics developed for this problem.     

A polyhedral approach to multicommodity survivable network design

Summary. The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and nonredundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. A cutting plane algorithm and heuristics for the problem are described, and preliminary computational results are reported. Received August 26, 1993 / Revised version received February 1994     

Incorporating congestion in preventive healthcare facility network design

Preventive healthcare aims at reducing the likelihood and severity of potentially life-threatening illnesses by protection and early detection. The level of participation to preventive healthcare programs is a crucial factor in terms of their effectiveness and efficiency. This paper provides a methodology for designing a network of preventive healthcare facilities so as to maximize participation. The number of facilities to be established and the location of each facility are the main determinants of the configuration of a healthcare facility network. We use the total (travel, waiting and service) time required for receiving the preventive service as a proxy for accessibility of a healthcare facility, and assume that each client would seek the services of the facility with minimum expected total time. At each facility, which we model as an M/M/1 queue so as to capture the level of congestion, the expected number of participants from each population zone decreases with the expected total time. In order to ensure service quality, the facilities cannot be operated unless their level of activity exceeds a minimum workload requirement. The arising mathematical formulation is highly nonlinear, and hence we provide a heuristic solution framework for this problem. Four heuristics are compared in terms of accuracy and computational requirements. The most efficient heuristic is utilized in solving a real life problem that involves the breast cancer screening center network in Montreal. In the context of this case, we found out that centralizing the total system capacity at the locations preferred by clients is a more effective strategy than decentralization by the use of a larger number of smaller facilities. We also show that the proposed methodology can be used in making the investment trade-off between expanding the total system capacity and changing the behavior of potential clients toward preventive healthcare programs by advertisement and education.     

Dynamic uncapacitated lot sizing with random demand under a fillrate constraint

This paper deals with the single-item dynamic uncapacitated lot sizing problem with random demand. We propose a model based on the “static uncertainty” strategy of Bookbinder and Tan (1988). In contrast to these authors, we use exact expressions for the inventory costs and we apply a fillrate constraint. We present an exact solution method and modify several well-known dynamic lot sizing heuristics such that they can be applied for the case of dynamic stochastic demands. A numerical experiment shows that there are significant differences in the performance of the heuristics whereat the ranking of the heuristics is different from that reported for the case of deterministic demand.     

Multi-Item Single-Level Capacitated Dynamic Lot-Sizing Heuristics: A General Review

The multi-item single-level capacitated lot-sizing problem consists of scheduling N different items over a horizon of T periods. The objective is to minimize the sum of set-up and inventory-holding costs over the horizon, subject to a capacity restriction in each period. Different heuristic approaches have been suggested to solve this difficult mathematical problem. So far, only a few limited attempts have been made to analyse and compare these approaches. The paper can be divided into two main parts. The first part shows that current heuristics can be classified in two different categories: single-resource heuristics, which are special-purpose methods, and mathematical-programming-based heuristics, which can usually deal with more general problem environments. The second part is devoted to an extensive computational review. The general idea is to find relationships between the performance of the heuristic and the computational burden involved in finding the solution. Based on these computational results, suggestions can be given with respect to the usefulness of the various heuristics in different industrial settings.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Heuristics for multi-period capacity expansion in local telecommunications networks

In this paper, different heuristics are devised to solve a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. This expansion is done by installing concentrators at the nodes and cables on the links of the network. The goal is to find a least cost capacity expansion strategy over a number of periods to satisfy the demand. A local search heuristic is first proposed to improve previously reported results on problem instances based on different cost and demand structures. This heuristic is then integrated into a genetic algorithm to obtain further improvements.     

有时间窗的车辆路径问题的局部下降搜索算法

介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.