A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

Dynamically similar control systems and a globally minimum gain control technique: IMSC

The concept of dynamically similar control systems is introduced. The necessary and sufficient conditions to minimize a quadratic modal gain measure are given for dynamically similar closed-loop control systems. The globally minimum modal gain is obtained when the independent modal space control (IMSC) is used. Corollaries of the results for the control of infinite-dimensional structural distributed parameter systems (DPS) are given. Based on the results, a modal interaction parameter (MIP) is defined for all control systems. The minimum value of MIP is zero and uniquely corresponds to the IMSC. A nonzero value of MIP corresponds to all other coupled control (CC) designs and implies suboptimality relative to the IMSC design. The relative optimality of the real-space gain matrices of the IMSC and the CC designs depends on the actuator locations for the IMSC. Based on this, a real-space interaction parameter (RIP) is defined. A positive value of RIP renders IMSC optimal in its real-space gain matrix. The MIP and RIP are indications of suboptimality of a particular control technique and can be used to tune-up the control design via actuator locations. Actuator distribution criteria are suggested for both CC and IMSC designs, based on the values of MIP and RIP, respectively.This work was supported by the National Science Foundation, Grant No. MEA-82-04920.     

The Adult Training Centre Problem: A Case Study

An optimal solution is found to a real-world problem which has the characteristics of a multiple travelling-salesman problem. It deals specifically with methods of obtaining the 'best' routeing for four vehicles which provide a daily service from a depot to 38 locations. The solution technique uses both heuristic and exact algorithms to derive the order for visits to the 38 locations.     

突发事件应急医疗物资调度的随机算法

传统的车辆路径问题(VRP)是为车辆设计将物资从仓库运送到各个需求客户的路线,使得总的运输费用(或时间)最小。在本文中,我们更关心的是使得未满足的需求量和总的物资延误时间最小。这个模型的一个非常重要的应用就是当大规模突发事件发生以后如何有效的将应急医疗物资运送到各个医疗单位,例如自然灾难,恐怖袭击之后,各个医院的医疗物资有限,需要从应急中心调集所需物资,在这种情况下,从应急中心分发应急物资过程中的运输费用就不再是最主要的考查因素,而更重要的是考虑物资到达医院的时间以及到达量,因为这两个因素直接与病人生命息息相关。本文的主要工作是改进了已有的局部搜索算法,通过引入随机算法的思想设计了求解模型的改进随机算法,可以得到模型更优的解,并通过计算机模拟案例说明了算法是行之有效的。     

A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays

In this paper, a probabilistic tabu search (PTS) approach is proposed to solve the facility layout problem (FLP) with unequal area departments. For the representation, the flexible bay structure (FBS), which is a very common layout in many manufacturing and retail facilities, is used. In this paper, the FBS is relaxed by allowing empty spaces within bays, which results in more flexibility in assigning departments into bays. In addition, departments are allowed to be located more freely within the bays, and they can have different side lengths as long as they are within the bay boundaries and do not overlap. To achieve these goals, department shapes and their locations within bays are determined LP. A PTS approach is developed to search an overall layout structure that describes relative positions of departments for the relaxed-FBS (RFBS). The proposed LP embedded PTS–RFBS approach is used to solve thirteen FLP instances from the literature with varying sizes. The comparative results show that this approach is very promising and able to find new best solutions for several test problems.     

Equilibrium network design of shared-vehicle systems

An equilibrium network design model is formulated to determine the optimal configuration of a vehicle sharing program (VSP). A VSP involves a fleet of vehicles (bicycles, cars, or electric vehicles) positioned strategically across a network. In a flexible VSP, users are permitted to check out vehicles to perform trips and return the vehicles to stations close to their destinations. VSP operators need to determine an optimal configuration in terms of station locations, vehicle inventories, and station capacities, that maximizes revenue. Since users are likely to use the VSP resources only if their travel utilities improve, a generalized equilibrium based approach is adopted to design the system. The model takes the form of a bi-level, mixed-integer program. Model properties of uniqueness, inefficiency of equilibrium, and transformations that lead to an exact solution approach are presented. Computational tests on several synthetic instances demonstrate the nature of the equilibrium configuration, the trade-offs between operator and user objectives, and insights for deploying such systems.     

The maximum reliability location problem and α-reliablep-center problem: Derivatives of the probabilistic location set covering problem

In the last several years, the modeling of emergency vehicle location has focussed on the temporal availability of the vehicles. Vehicles are not available for service when they are engaged in earlier calls. To incorporate this dynamic aspect into facility location decisions, models have been developed which provide additional levels of coverage. In this paper, two new models are derived from the probabilistic location set covering problem. These models allow the examination of the relationships between the number of facilities being located, the reliability that a vehicle will be available, and a coverage standard. In addition, these models incorporate sectoral specific estimates of the availability of the vehicles. Solution of these models reveals that the use of sectoral estimates leads to facility locations which are distributed to a greater spatial extent over the region to be serviced.     

Short-Term Capacity Adjustment with Offline Production for a Flexible Manufacturing System under Abnormal Disturbances

Large production variations caused by abnormal disturbances can significantly reduce the production capacity of a flexible manufacturing system (FMS). To prevent production delays, short-term capacity adjustment strategies can be used to augment the capacity of the FMS, such as working overtime, using alternative tools that are suited for faster processing, and producing parts outside of the FMS. We propose a mixed integer programming (MIP) model to obtain an optimal production plan for a multi-machine FMS. Our model evaluates both the FMS loading decision and the effective use of short-term capacity adjustment strategies to minimize the total part production cost. We develop an iterative procedure to solve the model that uses the Lagrangian relaxation method for finding lower bounds and a Lagrangian heuristic for obtaining feasible solutions. The procedure exploits certain special structures found in the Lagrangian multipliers which enable us to obtain good solutions to reasonably large test problems quickly.     

Terminal Location Problem: A Case Study Supporting the <Emphasis Type="Italic">Status Quo</Emphasis>

This paper applies a single-facility location model to the distribution network covered by the Brantford, Ontario branch of Thibodeau-Finch Transport Ltd. The model is used to determine whether or not the present terminal location should be maintained for the current demand structure and for a projected demand structure. Optimal locations are obtained for both demand structures using a distance function that is tailored to the actual road network over which the firm's vehicles travel. It is found that the transportation costs associated with the optimal locations are sufficiently close to those with the present location to conclude that Thibodeau-Finch should not consider relocation among its strategic options. The paper includes relevant data for verifying the conclusions drawn in support of the status quo.     

Operational Decisions in AGV-Served Flowshop Loops: Scheduling

This paper considers operational issues that arise in repetitive manufacturing systems served by automated guided vehicles (AGVs) in loops with unidirectional material flow. The objective considered is the minimization of the steady state cycle time required to produce a minimal job set (or equivalently, throughput rate maximization). Our models allow for delays caused by AGV conflicts. We define and analyze three nondominated and widely used AGV dispatching policies. For each policy, we describe algorithms and intractability results for combined job scheduling and material handling problems. We describe a genetic algorithm that estimates the cycle time within 5% on average for instances with up to 10 machines and four AGVs. Some related fleet sizing and loop decomposition issues are discussed in the companion paper [19].     

A memetic algorithm for the multiperiod vehicle routing problem with profit

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.     

An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations

In this study, we present a new formulation of the generalized flow-refueling location model that takes vehicle range and trips between origin–destination pairs into account. The new formulation, based on covering the arcs that comprise each path, is more computationally efficient than previous formulations or heuristics. Next, we use the new formulation to provide managerial insights for some key concerns of the industry, such as: whether infrastructure deployment should focus on locating clusters of facilities serving independent regions or connecting these regions by network of facilities; what is the impact of uncertainty in the origin–destination demand forecast; whether station locations will remain optimal as higher-range vehicles are introduced; and whether infrastructure developers should be willing to pay more for stations at higher-cost intersections. Experiments with real and random data sets are encouraging for the industry, as optimal locations tend to be robust under various conditions.     

A post-improvement procedure for the mixed load school bus routing problem

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.     

Survey of research in the design and control of automated guided vehicle systems

Automated guided vehicles (AGVs) are used for the internal and external transport of materials. Traditionally, AGVs were mostly used at manufacturing systems. Currently, AGVs are also used for repeating transportation tasks in other areas, such as warehouses, container terminals and external (underground) transportation systems. This paper discusses literature related to design and control issues of AGV systems at manufacturing, distribution, transshipment and transportation systems. It is concluded that most models can be applied for design problems at manufacturing centres. Some of these models and new models already proved to be successful in large AGV systems. In fact, new analytical and simulation models need to be developed for large AGV systems to overcome large computation times, NP-completeness, congestion, deadlocks and delays in the system and finite planning horizons. We specify more specific research perspectives in the design and control of AGV systems in distribution, transshipment and transportation systems.     

A Note on a Traffic Counting Distribution

In this paper the author formulates and derives a discrete traffic counting distribution and a passing rule which lead to bunches of zero or one “fast” vehicle behind a “slow” vehicle. “Slow” vehicles are distributed in a Poisson fashion and, except for those instants at which passing occurs, the constrained or “fast” vehicles follow immediately behind a “slow” one. The counting distribution is a simple example of one in which successive inter-vehicle spacings have the Markov property.     

Location-allocation planning of stockpiles for effective disaster mitigation

In the existing framework for receiving and allocating Strategic National Stockpile (SNS) assistance, there are three noticeable delays: the delay by the state in requesting federal assets, the delay in the federal process which releases assets only upon the declaration of a disaster and lastly the time it takes to reach supplies rapidly from the SNS stockpile to where it is needed. The most efficient disaster preparedness plan is one that addresses all three delays taking into account the unique nature of each disaster. In this paper, we propose appropriate changes to the existing framework to address the first two delays and a generic model to address the third which determines the locations and capacities of stockpile sites that are optimal for a specific disaster. Specifically, our model takes into account the impact of disaster specific casualty characteristics, such as the severity and type of medical condition and the unique nature of each type of disaster, particularly with regard to advance warning and factors affecting damage. For disasters involving uncertainty (magnitude/severity) with regard to future occurrences, such as an earthquake, development of appropriate solution strategies involves an additional step using scenario planning and robust optimization. We illustrate the application of our model via case studies for hurricanes and earthquakes and are able to outline an appropriate response framework for each.     

Optimization models for assessing the peak capacity utilization of intelligent transportation systems

With limited economic and physical resources, it is not feasible to continually expand transportation infrastructure to adequately support the rapid growth in its usage. This is especially true for traffic coordination systems where the expansion of road infrastructure has not been able to keep pace with the increasing number of vehicles, thereby resulting in congestion and delays. Hence, in addition to striving for the construction of new roads, it is imperative to develop new intelligent transportation management and coordination systems. The effectiveness of a new technique can be evaluated by comparing it with the optimal capacity utilization. If this comparison indicates that substantial improvements are possible, then the cost of developing and deploying an intelligent traffic system can be justified. Moreover, developing an optimization model can also help in capacity planning. For instance, at a given level of demand, if the optimal solution worsens significantly, this implies that no amount of intelligent strategies can handle this demand, and expanding the infrastructure would be the only alternative. In this paper, we demonstrate these concepts through a case study of scheduling vehicles on a grid of intersecting roads. We develop two optimization models namely, the mixed integer programming model and the space-time network flow model, and show that the latter model is substantially more effective. Moreover, we prove that the problem is strongly NP-hard and develop two polynomial-time heuristics. The heuristic solutions are then compared with the optimal capacity utilization obtained using the space-time network model. We also present important managerial implications.     

State constrained optimal control problems with time delays

In a recent, related, paper, necessary conditions in the form of a Maximum Principle were derived for optimal control problems with time delays in both state and control variables. Different versions of the necessary conditions covered fixed end-time problems and, under additional hypotheses, free end-time problems. These conditions improved on previous conditions in the following respects. They provided the first fully non-smooth Pontryagin Maximum Principle for problems involving delays in both state and control variables, only special cases of which were previously available. They provide a strong version of the Weierstrass condition for general problems with possibly non-commensurate control delays, whereas the earlier literature does so only under structural assumptions about the dynamic constraint. They also provided a new ‘two-sided’ generalized transversality condition, associated with the optimal end-time. This paper provides an extension of the Pontryagin Maximum Principle of the earlier paper for time delay systems, to allow for the presence of a unilateral state constraint. The new results fully recover the necessary conditions of the earlier paper when the state constraint is absent, and therefore retain all their advantages but in a setting of greater generality.     

Near-optimal MIP solutions for preference based self-scheduling

Making a high quality staff schedule is both difficult and time consuming for any company that has employees working on irregular schedules. We formulate a mixed integer program (MIP) to find a feasible schedule that satisfies all hard constraints while minimizing the soft constraint violations as well as satisfying as many of the employees’ requests as possible. We present the MIP model and show the result from four real world companies and institutions. We also compare the results with those of a local search based algorithm that is designed to emulate the solution strategies when the schedules are created manually. The results show that using near-optimal solutions from the MIP model, with a relative MIP gap of around 0.01–0.1, instead of finding the optimal solution, allows us to find very good solutions in a reasonable amount of time that compare favorably with both the manual solutions and the solutions found by the local search based algorithm.     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.