Emergency Logistics Planning in Natural Disasters

Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas as soon as possible so that relief operations are accelerated. In this study, a planning model that is to be integrated into a natural disaster logistics Decision Support System is developed. The model addresses the dynamic time-dependent transportation problem that needs to be solved repetitively at given time intervals during ongoing aid delivery. The model regenerates plans incorporating new requests for aid materials, new supplies and transportation means that become available during the current planning time horizon. The plan indicates the optimal mixed pick up and delivery schedules for vehicles within the considered planning time horizon as well as the optimal quantities and types of loads picked up and delivered on these routes. In emergency logistics context, supply is available in limited quantities at the current time period and on specified future dates. Commodity demand is known with certainty at the current date, but can be forecasted for future dates. Unlike commercial environments, vehicles do not have to return to depots, because the next time the plan is re-generated, a node receiving commodities may become a depot or a former depot may have no supplies at all. As a result, there are no closed loop tours, and vehicles wait at their last stop until they receive the next order from the logistics coordination centre. Hence, dispatch orders for vehicles consist of sets of “broken” routes that are generated in response to time-dependent supply/demand. The mathematical model describes a setting that is considerably different than the conventional vehicle routing problem. In fact, the problem is a hybrid that integrates the multi-commodity network flow problem and the vehicle routing problem. In this setting, vehicles are also treated as commodities. The model is readily decomposed into two multi-commodity network flow problems, the first one being linear (for conventional commodities) and the second integer (for vehicle flows). In the solution approach, these sub-models are coupled with relaxed arc capacity constraints using Lagrangean relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size.     

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.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

Clustering intelligent transportation sensors using public transportation

Advanced transportation sensors use a wireless medium to communicate and use data fusion techniques to provide complete information. Large-scale use of intelligent transportation sensors can lead to data bottlenecks in an ad-hoc wireless sensor network, which needs to be reliable and should provide a framework to sensors that constantly join and leave the network. A possible solution is to use public transportation vehicles as data fusion nodes or cluster heads. This paper presents a mathematical programming approach to use public transportation vehicles as cluster heads. The mathematical programming solution seeks to maximize benefit achieved by covering both mobile and stationary sensors, while considering cost/penalty associated with changing cluster head locations. A simulation is developed to capture realistic considerations of a transportation network. This simulation is used to validate the solution provided by the mathematical model.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

Optimizing solid waste collection in Brussels

This paper reports on a project dealing with waste collection management. A methodology used in this case study combines an operations research method with systems engineering. It illustrates how waste transportation costs are minimized in a major urban area. Due to the complexity of a real size situation, a model is developed to consider a set of points for the collection routes rather than the arcs making up the streets. Several means of transportation including transportation by vehicle, rail and canal are evaluated. Collector vehicles reside overnight in depots and daily evacuate accumulated waste to an incinerator or a transfer station where it is deposited before being shipped out to the incinerator. The latter two sites are called terminal sites. Although optimization models are too difficult to solve with existing means, useful collection strategies are found to give some grounds to decisions made by urban administrators.     

A dynamic network loading model for mesosimulation in transportation systems

Flow propagation models can be divided into static and dynamic network loading models. Different approaches to dynamic network loading problem formulated in the literature point out models that can be classified as disaggregate or aggregate.Applying aggregate models, it is possible to trace implicitly or explicitly vehicles movements. The second case concerns mesoscopic models. These models consider the traffic as a sequence of “packets” of vehicles. Two approaches can be followed:

• (a)continuous packets, where vehicles are distributed inside each packet, defined by the head and the tail points;
• (b)discrete packets, where all users belonging to a packet are grouped and represented by a single point, for instance the head.

In this paper, a mesoscopic model based on discrete packets has been developed, taking into account the vehicles acceleration. The proposed model, assuming discrete packets and uniformly accelerated movement, appears lifelike in the representation of outflow dynamics and quite easy to calculate.     

考虑车辆限速区间的危险品运输网络优化

由于危险品在运输过程中存在极大的危害性,为了降低危险品运输风险,政府可以通过对不同路段设置不同的限速区间来引导危险品运输车辆的路径选择,从而导致不同的运输网络总风险和鲁棒成本。首先基于车辆限速区间的方法,构建了危险品运输网络优化的双层规划模型,上层规划以最大运输网络总风险值最小化为目标,下层规划以危险品运输企业的鲁棒成本最小化为目标;然后,设计了粒子群优化算法求解了该模型;最后,通过两个算例验证了模型和算法的有效性。计算结果表明政府部门运用车辆限速区间的方法不仅能够非常有效地降低危险品运输网络总风险,而且更具有鲁棒性和现实可操作性。     

A GPSS/H model for a hypothetical flexible manufacturing system

A GPSS/H model is presented for a hypothetical flexible manufacturing system. The FMS consists of six machines composed of three machine types, manufactures three types of parts, and uses automatic guided vehicles (AGVs) to transport inprocess parts between appropriate machines and wait spaces in the system. Three logical modules have been designed for the model, with copies of these modules then being appropriately distributed and interfaced throughout the model and tailored to achieve overall representation of the specific FMS. The same technique can be used by others to build analogous or extended GPSS/H models for other specific FMSs in which AGVs are used as transporters. Simulations can then be performed with such models to research FMS design and control alternatives.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

Minimizing the passengers’ traveling time in the stop location problem

In this paper we consider the location of stops along the edges of an already existing public transportation network. The positive effect of new stops is given by the better access of the passengers to the public transport network, while the passengers’ traveling time increases due to the additional stopping activities of the trains, which is a negative effect for the passengers. The problem has been treated in the literature where the most common model is to cover all demand points with a minimal number of new stops. In this paper, we follow this line and seek for a set of new stops covering all demand points but instead of minimizing the number of new stops we minimize the additional passengers’ traveling time due to the new stops. For computing this additional traveling time we do not only take the stopping times of the vehicles but also acceleration and deceleration of the vehicles into account. We show that the problem is NP-hard, but we are able to derive a finite candidate set and two tractable IP formulations. For linear networks we show that the problem is polynomially solvable. We also discuss the differences to the common models from literature showing that minimizing the number of new stops does not necessarily lead to a solution with minimal additional traveling times for the passengers. We finally provide a case study showing that our new model decreases the traveling times for the passengers while still achieving the minimal number of new stops.     

Evaluation and optimization of urban public transportation networks

So far, not much attention has been given to the problem of improving public transportation networks. In many cities these networks have been built sequentially and do not fit to the needs of the users any more. The results are long travel times and an unnecessarily high number of people who have to transfer. Compared to other investments for improving the service level of public transportation systems, the costs of rerouting the public vehicles are low and can, yet, highly improve the performance of the system.To evaluate a public transportation network, the shortest distance and the shortest route from node x to node y, taking the waiting times for a vehicle into account, must be known.It is shown in this paper, how to compute distances and routes efficiently for large networks. Using this algorithm it is described how to evaluate the average transportation cost of the passengers in a public transportation network.In the second part of the paper a heuristic algorithm is stated that improves a public transportation network using the average transportation cost as the objective.Finally, some experiences with real world problems are reported.     

Locating replenishment stations for electric vehicles: application to Danish traffic data

Environment-friendly electric vehicles have gained popularity and increased attention in recent years. The deployment of a network of recharging stations is essential given their limited travel range. This paper considers the problem of locating electronic replenishment stations for electric vehicles on a traffic network with flow-based demand. The objective is to optimize the network performance, for example to maximize the flow covered by a prefixed number of stations or to minimize the number of stations needed to cover traffic flows. Two integer linear programming formulations are proposed to model the problem. These models are tested on real-life traffic data collected in Denmark.     

Synchronizing production and air transportation scheduling using mathematical programming models

Traditional scheduling problems assume that there are always infinitely many resources for delivering finished jobs to their destinations, and no time is needed for their transportation, so that finished products can be transported to customers without delay. So, for coordination of these two different activities in the implementation of a supply chain solution, we studied the problem of synchronizing production and air transportation scheduling using mathematical programming models. The overall problem is decomposed into two sub-problems, which consists of air transportation allocation problem and a single machine scheduling problem which they are considered together. We have taken into consideration different constraints and assumptions in our modeling such as special flights, delivery tardiness and no delivery tardiness. For these purposes, a variety of models have been proposed to minimize supply chain total cost which encompass transportation, makespan, delivery earliness tardiness and departure time earliness tardiness costs.     

A neural network model for enhanced operation of midblock signalled pedestrian crossings

UK transport policy has shifted dramatically in recent years. The new policy direction to promote walking as an alternative to car for short trips. Midblock signalled pedestrian crossings are a common method of resolving the conflict between pedestrians and vehicles. This paper considers alternative operating strategies for midblock signalled pedestrian crossings that are more responsive to the needs of pedestrians without increasing the delay to motorists and freight traffic. A succession of artificial neural network (ANN) models is developed and factors influencing the performance of pedestrian gap acceptance models both in terms of accuracy and processing requirements are considered in detail. The paper concludes that a feedforward ANN using backpropagation can deliver a gap acceptance model with a high degree of accuracy with acceptable constraints.     

Dynamic TCP acknowledgment in the LogP model

When messages, which are to be sent point-to-point in a network, become available at irregular intervals, a decision must be made each time a new message becomes available as to whether it should be sent immediately or if it is better to wait for more messages and send them all together. Because of physical properties of the networks, a certain minimum amount of time must elapse in between the transmission of two packets. Thus, whereas waiting delays the transmission of the current data, sending immediately may delay the transmission of the next data to become available even more. We propose a new quality measure and derive optimal deterministic and randomized algorithms for this on-line problem.     

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.     

Delivery delay variation in multi-echelon inventory problems

Mathematical models for controlling multi-echelon inventory and production levels have been developed for entire interconnected systems rather than myopically for each point in the inventory or production system. With such models come the additional burden of considering the lead times and delays associated with the movement of items through the network. The delays develop when a backorder state occurs and are often considered in models by approximating the mean delay by an application of Little's Law and without consideration of the delay variation. In this article a general methodology for incorporating the variation of the delay is derived and incorporated into a backorders optimisation model. The result of incorporating delay variation into the model is a tolerance interval for order quantities that may be utilised for tighter inventory control.     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

Integrating transportation and production: an international study case

The problem we study is inspired by the real case of Mesdan S.p.A., an Italian company worldwide leader in the textile machinery sector, which has two production units with two warehouses, one located in Italy (Brescia) and the other in China (Foshan). The critical point in this logistic system is the integration between production and transportation management, given the long distance between Brescia and Foshan. Shipments are performed by the means of different types of vehicles with different unit costs and significantly different lead times. Variable production costs, variable and fixed transportation costs and, possibly, inventory costs are charged in the objective function. Different production policies are compared. Our aim is to determine integrated policies that minimize the total cost of the system. We formulate integer linear programming models for the solution of these problems, and we solve the real instance and carry out a sensitivity analysis of the optimal solution.