自然灾害中的应急物流规划【外文翻译】.doc

1、外文翻译 原文 Emergency Logistics Planning in Natural Disasters Material Source: SpringerLink Author: Linet Ozdamar Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution

2、 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

3、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

4、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 d

5、ates. 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

6、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

7、 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 ow problem and the vehicle routing problem. In this setting, vehicles are also treated

8、 as commodities. The model is readily decomposed into two multi-commodity network ow problems, the rst one being linear (for conventional commodities) and the second integer (for vehicle ows). In the solution approach, these submodels are coupled with relaxed arc capacity constraints using Lagrangea

9、n relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size. This study is concerned with planning logistics at a macro level in the presence of natural disasters. The research is motivated by the re-organisation pr

10、oject of the Turkish Armed Forces Natural Disaster Coordination Centre that was activated after Izmit and Duzce earthquakes in 1999. The logistics planning model proposed here is intended to be a component of a Logistics Decision Support System linking all relevant databases (stocking units, aid dis

11、tribution centres, national transportation networks,search and rescue teams, etc.)and the central aid coordination centre.Macro level logistics planning in emergencies involves inter-city transportation of commodities, such as medical aid materials and personnel, specialized equipment,troops to keep

12、 order and to conduct rescue activities, food and other commodities used in relief operations. The coordination centre decides on the quantities, origins, and destinations of relief commodities to be transported, and on the specic vehicles to be dispatched to carry these commodities. At the time of

13、planning, vehicles of different types (ground, air, rail, etc.) and capacities might be free at supply centres, demand centres,or at other locations. Thus, transportation plans made for the commodities are accompanied by vehicle sched ules that designate the type, number, route and mobilization timi

14、ng of selected vehicles. The logistics plan involves a planning time horizon consisting of a given number of time periods because it deals with time-variant demand and supply. During a given planning horizon, the model assumes that demand is known for the initial period of the current planning time

15、horizon, and, future demand is forecasted for some commodities. Supply is limited and its availability is known for some periods ahead due to the fact that prospective supply arrivals are usually known in advance. At the beginning of any planning time horizon, given a snapshot of current and future

16、requirements/supplies,and vehicle availability, the plan generates multi-period vehicle routes/schedules along with their commodity load-unload assignments. During ongoing relief operations, vehicles are not required to return to supply centres (depots) when their assignments are completed for the g

17、iven planning time horizon. Rather, once they reach their nal destination, they wait for the next order at their current locations, because it is not certain that a depot will have available supplies at the next planning period. This is typical in emergencies and therefore, one cannot adopt the conv

18、entional concept of a “vehicle route”in this model. Furthermore, during its scheduled assignments, a vehicle might pick up commodities and deliver goods as well, because it is also possible to have supply centres (stocking units) in the affected area. Therefore, this distribution problem does not ne

19、cessarily imply a topology where there exists a cluster of centres receiving aid from unaffected cities outside the region of emergency. The plan is updated at regular time intervals incorporating new information on demand, supplies and vehicle availability, and, accounting for the status of the log

20、istics system resulting from the plan implemented previously. Since the plan has a time-dependent structure, re-planning is facilitated and is carried out repeatedly during ongoing disaster relief operations. Thus, the system is designed to respond to time-dependent logistic needs in an adaptive man

21、ner, so that after the emergency call is announced, it responds quickly to new demand, supply and vehicle availability. Given the aspects mentioned above, the problem is classied as a hybrid problem integrating the multi-period multi-commodity network ow problem with the vehicle routing problem. In

22、the proposed model, vehicles are also treated as commodities that accompany the actual goods. Thus, the problem is converted into a mixed integer multi-period multi-commodity network ow problem where the integer part represents the vehicles. Although the model is compact and the problem size is redu

23、ced signicantly in terms of the number of integer variables, it may become intractable when dealing with very large scale emergencies. Therefore, an iterative solution approach based on Lagrangean relaxation is proposed. The efciency of the proposed algorithm is demonstrated on randomly generated sm

24、all test problems as well as on an earthquake scenario of realistic size. The algorithm is also compared to a greedy heuristic designed specically for this problem. The paper is organized as follows. First, the problem at hand is analysed and its relevance to well-known problems in the literature is

25、 discussed. Next, a mathematical formulation of the problem is developed and its use in dynamic environments is explained. The output of the model is illustrated with a small example. Then, a solution methodology that involves decomposition and Lagrangean relaxation is described.Finally, numerical r

26、esults are presented. 2. Analysis of the problem The problem at hand is related to the vehicle routing problem (VRP) discussed extensively in the literature. In the VRP, a number of customers (each represented as a destination node) are served by m identical vehicles located at a depot. Each vehicle

27、 returns to the depot after completing its trip (tour). The load of a vehicle cannot exceed its capacity on any tour. Furthermore, a customer can be visited only once and it is assumed that a vehicles load capacity exceeds every customers demand. The aim is to determine vehicle routes resulting in t

28、he minimum total travel distance. The denition of the VRP implies that the quantity of commodity to be transported to every destination pair is known and sufcient supply is always available at the depot to satisfy all customer demand. The restrictive assumptions of the VRP are often relaxed to accom

29、modate more realistic settings. A customer may be visited more than once if demand exceeds the load capacity of available vehicles. This feature is known as split delivery. Dror and Trudeau (1990) propose heuristics for the split delivery VRP where routes are broken and re-combined to improve the so

30、lutions obtained. In some relaxed VRPs, vehicles can deliver and pick up commodities on the same tour, however, they cannot carry more than one order at a time. This approach is called the mixed delivery approach. Another relaxation involves having multiple depots. Surveys on the VRP and its extensi

31、ons can be found in Desrochers et al. (1988) and Bodin (1990). In Desrochers et al. (1990), each type of VRP is classied according to several characteristics: (i) addresses (demand locations to be satised, their number, sets of demand clusters to be satised etc.); (ii) vehicles (homogeneous/heteroge

32、neous eet, xed or variable eet size, time windows for vehicle availability); (iii) service strategy (issues such as split delivery, mixed delivery, precedence constraints between demand locations, time windows); and (iv) objectives (address penalty implying the deviation from preferred service level

33、, or, vehicle penalty implying eet size and costs).More recently, Desrochers et al. (1998) propose an automatic model base and algorithm selection system that is implemented according to problem characteristics. Extensive discussions of heuristic and optimisation algorithms are given in Laporte (199

34、2) and Fisher (1995) for a variety of vehicle routing problems. Recent examples of local search heuristics (e.g., simulated annealing, tabu search, etc.) designed for solving the VRP can be found in Rodriguez et al. (1998) and Gendreau et al. (1999). The emergency logistics coordination problem desc

35、ribed here is modeled as a mixed integer multi-commodity network ow problem. Two previous VRP related studies that treat vehicles as commodities are summarized below. Ribeiro and Soumis (1994) treat vehicles as commodities in their multi-depot nonsplit delivery VRP. In their model, trips are predete

36、rmined and it is required to assign one vehicle to every trip. The authors show that the LP relaxation of their formulation provides a good lower bound for the integer problem. Fisher et al. (1995) also represent vehicles as commodities in the mixed delivery VRP where each vehicle is restricted to c

37、arry one order at a time. Hence, the VRP under consideration is converted into a network ow problem. The authors approximate the loads to be transported into integer truckloads for simplication purposes. As a result of their modeling approach, the solution may have infeasible cycles. These are repai

38、red by adding the depot in a cycle, or,by merging/splitting two cycles. 译文 自然灾害中的应急物流规划 资料来源 :SpringerLink 作者： Linet Ozdamar 物流规划涉及 了 紧急情况影响 下 地区派遣商品（如医疗物资和人员，专业救援设备和救援队，食品等），配送中心，使救援行动尽快 加速运行 。在这项研究中，规划模型，将自然灾害纳入 发达的物流 决策支持系统。该模型解决了动态时间相关的运输问题，需要加以解决 在 给定的时间间隔 里 反复 存 在 不间断进行 援助的运送。该模型纳入援助再生材料计划，新物资

39、和运输工具成为在目前的跨度规划时间 里 可利用的新要求。该计划表明了最优混合挑了起来，在 考虑规划的时间范围以及车辆的最佳数量 时 拿起负载 的类型 和交货时间表 在 路线上传递。在紧急情况下的物流 运输中 ，在当前一段时间 和 在指定的未来日期 内 供应数量 是 有限。 商品的需求是在目前已知的日期确定，但可以预测未来的日期。不同于商业环境，车辆不必返回仓库，因为下一次的计划是重新生成，节点接收商品可能成为一个仓库或仓库前可能毫无供应。因此，有没有闭环之旅，并在他们的最后一站的车辆等待，直到他们收到来自后勤协调中心旁的顺序。因此，派出车辆订单的 “破 ”的路线是在响应时间依赖的供应 /需求产

40、生套组成。该数学模型描述的设置是大大 高于传统的车辆路径问题的不同。其实，这个问题是一个 复杂的 ，融合了多商品网络流问题，车辆调度问题。在这种背景下，车辆也被视为商品。该模型是很容易分解成两个多商品网络流问题，第一个是线性的（常规商品），第二个整数 的 （车辆流量）。在解决方案的方法，这些子模型的能力，再加上宽松的弧使用拉格朗日松弛的限制。建议中的算法的收敛性测试小测试实例，以及关于地震的实际大小情况。 车辆路径问题根据服务时间窗限制又可以分为软时间窗问题和硬时间窗问题，其中软时间窗车辆路径问题表示如果车辆无法在要求的时间窗内将货物送达需求点，则必须支付一定的惩罚费用；硬时间窗车辆路径问题表

41、示车辆必须在规定的时间内将物资送达应急需求点，不论是早到或迟到都完全被接受。应急情况下的车辆路径问题与一般的车辆路径问题的区别是应急车辆出行的目的是为了到达需求点进行救助等活动，所实施的是应急事件，凸显的是其时间紧迫性，并且只有时间窗得到满足的情况下才能达到其应急的效果，否则在时间窗外到达应急需求点，它的效用明显降低。此 外对应急车辆早到达应急需求点的时间要求没有限制条件，早到早服务进而提高其救援效率。应急物资可提前到达，但是不能迟于规定时间。 本研究关注的是在自然灾害面前宏观物流 的规划 。这项研究的动机是由土耳其武装部队的自然灾害协调中心和迪兹杰后伊兹米特地震启动于 1999年重新组织项目

42、。物流规划提出的模型在这里的目的是成为一个物流决策支持系统组件连接所有相关的数据库（库存单位，物资发放中心，国家交通运输网络，搜索和救援队等）和中央援助协调 中心。 在紧急情况级物流规划涉及城际如医疗援助物资和人员，专门设备，部队维持秩序和进行救 援活动，食品和其他商品的救援行动中使用的商品，运输。该协调中心决定在数量，来源，以及救援物资运送到目的地，并在特定的车辆将派出携带上述商品。在规划时，不同类型（地面，空中，铁路等）和能力的车辆可能会免费供应中心，需求中心，或在其他地方。因此，运输计划的商品取得都伴随着车辆排程的指定类型，数量，路线和动员时机选择的车辆。计划涉及的物流规划的时间范围的一

43、个特定的时间段，因为它涉及的时变需求和供应量组成。在给定的规划范围，该模型假设的需求而闻名目前规划的时间跨度初期，以及未来需要的是一些商品预测。 在任何规划的时 间跨度开始考虑对目前和未来的需求 /供应的快照，和车辆可用性，以及该计划产生它们的商品加卸载作业多期车辆路线 /时间表。在正在进行的救援行动，车辆不须返回供应中心（站）时，他们的任务是给定的时间范围内完成规划。相反，一旦达到他们的最终目的地，他们等待下一个订单在现有的位置，因为它不是某一个车厂将在下次规划期内可供应。这是典型的，因此在紧急情况下，不能采取一个 “车辆路线 “这一模式的传统观念。此外，在其预定任务，车辆可能会选择提供商品

44、和货物很好，因为它也有可能在受影响地区的供应中心（库存单位）。因此，这种分配问题并 不一定意味着那里存在着一个拓扑接收来自区域外的紧急援助中心的城市群不受影响。 该计划是在固定的时间更新的需求结合，用品和车辆提供新的信息的时间间隔，并为实施的后勤服务，从以前的计划造成的系统状态核算。由于计划有一个随时间变化的结构，重新规划提供便利，并开展了救灾工作的过程中不断反复。因此，该系统是为了响应随时间变化的物流需要一个自适应的方式，这样的紧急呼叫后宣布，它迅速响应新的需求，供应和车辆可用性。 鉴于上述问题，该问题被归类为一体的混合多期与车辆路径问题多商品网络流问题的问题。在提出的模型，车辆也被视为 商

45、品，伴随实际货物。因此，问题转化为一个混合整数多期多商品网络流问题，即整数部分代表的车辆。 虽然该模型是紧 凑 的， 但是 减少了整数变量的数目方面 的 问题 是显著的 ，它可能成为棘手时具有非常大规模紧急情况处理 的办法 。因此， 在 代求解方法上，提出了基于拉格朗日松弛。该算法的有效性是 根据 展示的测试问题随机生成的，以及对地震大小的一个现实情况。该算法也 是为了 贪婪启发式这个问题专门设计的。 本文的结构如下 ， 首先， 对 目前的问题进行了分析，讨论的问题 是 其相关的文献中众所周知的。接下来，对这个问题的数学公式 、 开发及在动态环境中使用的解释。用一个小例子说明该模型的输出。然后，求解方法，分解涉及和拉格朗日松弛 有关的计算，最后 ， 求出 数值结果。