A Simulation-Driven Approach for a Cost-Ef?cient Airport Wheelchair Assistance Service 一个用于低费用的飞机场轮椅服务的激励驱动的方法
Samuel F. Feng Tobin G. Isaac Nan Xiao Rice University Houston, TX
Advisor: Mark P. Embree
Summary 摘要
Although roughly 0.6% of the U.S. population is wheelchair-bound, the strain of travel is such that more than twice that amount relies on wheelchairs in airports [Haseltine Systems Corp. 2006]. 尽管大约0.6%的美国人口是需要轮椅的，但是旅行中的经常会有大约1.2%的人使用轮椅。 Two issues have the greatest impact on the cost and effectiveness of this service: the number of wheelchairs and how they should be deployed. 两个问题对于这项服务的费用和效果有巨大的影响：轮椅的数量，他们如何布置。 The proper number of escorts and wheelchairs is not only a question of the airport but of the volume of passengers, which can vary greatly. 托运者和轮椅的合适数量不只是飞机场的问题，也与乘客数量有很大关系，因为乘客的变化很大。 If escorts determine their own movements within the airport, lack of coordination could result in areas being unattended; however, ?uctuation in requests could be so great that a territory-based plan could overwork some escorts and underwork others. 如果托运者在飞机场里决定他们自己的行动，缺乏协调可能导致空间里用不足；但是，需求的波动很明显，以至于以地区为准的计划
可能会过度利用一些托运者并且使其他人工作不足。 We present an algorithm for scheduling of the movement of escorts that is both simple in implementation and effective in maximizing the use of avail- able time in each escort’s schedule. 我们提出一个算法来调度托运者的行动，实现起来很简单，在最大化利用可用时间来调度托运者方面的效率也很高。 Then, given the implementation of this algorithm, we simulate the scheduling of requests in a given airport to ?nd the number of wheelchair/escort pairs that minimizes cost. 给出一个这个算法的实现，我们在一个给定的飞机场模拟请求的调度，来找出使得费用最低的轮椅和托运者配对的数量。
Methods And Assumptions 方法和假设 We propose a stochastic simulation-driven optimization procedure. 我们提出一个随机的模拟的最优化步骤。 We partition the problem into three categories: pre-simulation processing, simulation rules and dynamics, and optimization. 我们把这个问题分为三个范畴：事先的模拟步骤，模拟规则和动态，最优化。 The pre-simulation phase generates the necessary inputs for the simulation phase, such as the airport layout and a master passenger request list containing the wheelchair assistance requests for a single day. 事先的模拟阶段为模拟阶段产生必要的输入，比如机场布局和一个总的顾客需求列表，包括了一整天的轮椅需求。 The simulation phase consists of a continuous event-based model of passenger arrival/departure and wheelchair/escort movement. 模拟阶段包括了一个连续的基于事件的顾客到达离开以及轮椅托运者的移动的模型。 Finally, we minimize costs over the number of escorts. 最后，我们最小化托运者的费用。 Pre-Simulation 事先模拟 Airport Layout 机场布局 The simulation is customized for the layout of each airport. 模拟为每一个机场的布局定制。 We represent an airport as a bidirectional graph, in which nodes indicate gates, entrance/exit points, or other places of similar interest. 我们把每一个机场看做一个双向图，其中节点代表了门，出入口地点，或者其他相似的地方。 Edges between nodes indicate travel paths, usually through the main hallway of a concourse. 节点之间的边代表了旅行线路，通常穿过大厅的主要道路。 We constructed the graphs with the aid of satellite images [Google.com n.d.]. 我们借助卫星图片的帮助来构建图形。 Passengers must travel through long corridors to reach departure gates. 顾客不许通过长长的门廊来到达出站的大门。 A typical concourse has gates on either side of the main corridor. 典型的大厅在主走廊的两边都有大门。 We assume that the time required to travel from any gate to any gate is substantial; that is, even if two gates are adjacent or on opposite sides of the main corridor, we assess the travel time between the two gates. 我们假定从任何一个门任何另一个门所需要的时间是大量的；也就是说，尽管两个门挨着或者在住走廊的两边相对着，我们都要估算
两个门之间穿梭的时间。 The graphical representation of the airport is encoded in an n ×n adjacency matrix A, with entry Ai,j denoting the travel time between location i and lo- cation j 飞机场的图形表示被编码成一个n*n的邻接矩阵A，Ai，j条目代表着i和j之间的穿梭时间。 . We determine travel times by ?guring the actual distance divided by a walking speed of 3 mph. 我们通过计算实际距离来决定穿梭次数，步行速度定位3mph。 The shortest possible travel times (calculated using Dijkstra’s algorithm [Wang 2006]) from every location to every other lo- cation is referenced in matrix D, with entry Dij denoting the shortest travel time between nodes i and j . 最短的可能穿梭次数（通过dijkstra算法计算）通过每一个地点到另一个其他的地点，存在矩阵D中，条目Di，j表明了i和j之间的最
短穿梭时间。 We assume that the escorts know the shortest path between any two gates, because they are familiar with the airport environment. In our simulations we do not consider the distance between the gate and the airplane. 我们假定托运者知道两个门之间的最短的路线，因为他们熟悉飞机场环境。在我们的模拟中，我们不考虑门和飞机场之间的距离。
Wheelchairs And Escorts 轮椅和托运者 We treat a wheelchair and its escort as a single traveling entity, the “escort.” 我们把每对轮椅和托运者看做一个单独的移动实体，“escort”。 The airline may have additional wheelchairs on hand in the event of a mal- function, and we incorporate the cost of the additional wheelchairs into the maintenance and storage costs of wheelchairs in operation. 航空公司手上可能有附加的轮椅，以应对故障事件，我们把这些附加的轮椅的费用并入维护费用以及轮椅的存储费用。 The escort’s job is to travel to the arrival gate of the passenger and transfer the passenger to the departure gate. 托运者的工作就是向顾客到达的门移动，然后把顾客带到离开的门。 An important assumption is that the number of escorts remains constant throughout the simulation period. 一个重要的假设就是托运者的数量在整个模拟期间保持稳定。 In reality, escorts rotate in shifts; but with a simulation period of one day, we assume that escorts starting a shift imme- diately replace escorts ending one. 现实中，托运者会轮班；但是在一天的模拟期中，我们假定一个工作结束后，另一个立即代替开始轮班。 Similarly, during the simulation we do not allow hiring or firing of workers, nor buying or breaking of wheelchairs; in- stead, we represent the costs associated with these actions with a sunken cost term in the total cost function. 相似的，在模拟中，我们不允许雇佣或炒鱿鱼，不会买进新的轮椅，也不会破坏现有的轮椅；相反，我们把这类行为带来的费用用一
个总费用函数中的凹陷费用来代表。
Passenger Request List 顾客请求列表 Given a terminal, we create a flight schedule for one day. 给定一个terminal，我们造一个一整天的飞行调度。 We look at the total number of passengers who pass through the airport in one day. 我们看一下那些一天内穿越飞机场的乘客的总数。 We estimate the average load of a plane to be 125 passengers, which we use to estimate the number of flights arriving or departing at the terminal in one day. 我们假定一个飞机平均载客量为125，我们用来估计一天内terminal里航班起飞和落地的数量。 Observation of departing flight information at a busy airport [City of Atlanta 2006] con?rms the information in another source [Neufville 1976]: There is regular activity between 6 a,m, and 10 p.m. and relatively few ?ights at night. 在一个繁忙的飞机场的离港航班信息（2006年亚特兰大）的观察证实了另一个信息来源（1976年纽维尔）：在上午6点和晚上十点之
间会有一个比较规律的活动，夜晚的航班相对较少。 We therefore space our departures evenly between these times, and then perturb these values by a random shift of less than an hour, so that we are certain not to test our algorithm against just one schedule. 我们因此把我们的离港平均的分在这些次数里，然后通过一个一小时之内的随机的变化扰动这些值，这样我们肯定不会用一个调度来
检验我们的算法。 Subsequently, these ?ights are assigned to speci?c gates. 随后，这些航班被分到特定的大门。 Next, we create the requests for the day. 接下来，我们为每一天制造一些请求。 We generate the number of requests based on the passenger volume that we are trying to mimic and the percentage of the population that requires wheelchair assistance. 我们基于之后会试图模仿的乘客体积和需要轮椅服务的百分比来产生请求的数量。 For different runs, this value was either 0.6% or 1.2% [Haseltine Systems Corp. 2006]. 每一次不同的运行，这个值是0.6%或者1.2%。 Each request is assigned an arriving ?ight and a departing ?ight, with the assumption that no layover of less than half an hour should be attempted. 每一次请求被分配一个快到达的航班和一个正在离开的航班，没有少于一个小时的的layover。 We assume that a certain percentage of wheelchair passengers have phoned the airline ahead of time; time of request is set to 0. For the remainder, we generate random request times, varying from more than ?ve hours to a half hour before arrival of the wheelchair passenger. 我们假定特定比例的轮椅乘客事先给航空公司打了电话；请求的时间被设置为0.对于剩下的人，我们产生一个随机的请求时间，从轮
椅乘客的到达之前的5个小时到一个小时之间不等。 We sort this list by request time, so that when the algorithm descends the list, it mimics a dispatcher’s receiving the requests at varying times throughout the day, including the wheelchair needs that occur with little notification. 我们通过请求时间来排列这个序列，当算法作用于序列时，他模仿了一个分配者在一天内接受不同时间的请求，包括了几乎没有任何
通知的轮椅需求的发生。 Different daily scenarios can be modeled by altering the generation of the request list. 每天不同的情景通过改变请求序列的产生来建立模型。 The request list models the passenger traf?c load throughout the simulation, since it contains a greater concentration of requests during peak hours of operation. 请求序列模拟了乘客的吞吐量，因为它包括了在高峰期的请求更大的集中化。 Furthermore, request frequency throughout the day can be increased to re?ect operation during holiday-travel seasons at hub airports, or yearly peak-travel at airports in popular vacation destinations. 此外，一天里的请求频率可以增加来反映假期时枢纽飞机场的情况，或者每年在旅游目的地飞机场的高峰期。
Scheduling Plan 调度计划 We assume that escorts communicate with a dispatcher via a walkie-talkie, and that the dispatcher has a schedule for each escort. 我们假定托运者通过一个步话机与分配者来通信，分配者对于每一个托运者有一个调度。 An escort who has completed a task calls the dispatcher to ?nd out the next. 完成了任务的托运者报告分配者来找出下一个。 We assume that the dispatcher knows how long it takes an escort to get between two points x and y, which we call δxy . 我们假定分配者知道一个托运者在x，y之间移动的时间，我们把它称为δxy。 A dispatcher receives requests at varying times throughout the day. 分配者在一天内不同的时间受到请求。 Each request contains four pieces of information: the time and location of the pas- senger’s arrival, ta and a, and the time and location of departure, td and d. 每一个请求包括了四部分信息：顾客到达的时间和地点（ta，a），离开的时间和地点（td，d）。 For the passenger to reach the destination in time, the escort must arrive at a location by some final time, 对每一个及时到达目的地的顾客，托运者必须在某个时间（tf）内到达地点。 tf = td - δad .
The algorithm’s version of “?rst come, ?rst served” is that one task cannot replace another on a schedule if its ?nal time is later. 先来先服务的算法版本是，一个调度中，一个finaltime晚一些的任务不能取代另一个。 This keeps every schedule compact: If a switch is made, the only result is the new task starting sooner after the previous one (switching will be discussed shortly). 这保证了每一个调度的作用：如果一个转换做出，唯一的结果就是新的任务在前一个结束后开始的更早（转换将会在后面考虑）。 To determine which escort should be assigned a passenger, the dispatcher ?rst ?nds out if anyone can complete the task. From those who can, he selects one who can complete it in an optimal way, as follows. 为了决定哪一个托运者分配给哪一个顾客，分配者首先看下是否有人能够完成任务。从那些可以完成的人中，选择那个最优的人来完
成。 The worst way in which a request can be ful?lled is for the escort to bring the passenger to his destination late yet within the window δw in which the ?ight is delayed. 那些请求可以被满足的方式中最坏的一个，就是让托运者把乘客带到目的地迟了，没能赶在在窗口之前，窗口δw就是飞机被延误的
窗口。 To determine if escort e can do this, the dispatcher looks at what location le the escort will be at completion of the last job before the ?nal time of the request, and when that job will be completed, te. 为了决定一个托运者是否可以做到这样，分配者看看托运者的完成最后一个工作的地点le，还有什么时候 te这个工作完成。 We need 我们需要 te + δea < tf + δw .
An escort who meets this requirement is in group O1. 那些可以满足这个请求的托运者在01组里。 A better way in which a request can be fulfilled is if an escort can bring the passenger to the destination on time but by removing another passenger from his schedule later. 一个请求可以被满足的更好的方式，是如果一个托运者可以把乘客及时带到目的地但是得把另一个乘客从他的调度中移除。 The condition for this one is the same as above, but without the delay term: 这种情况下与前面的一样，但是不需要飞机延误δw： te + δea < tf .
An escort who meets this requirement is in group O2. 一个满足这个要求的托运者在分到02组里。 Because we want to do as little reshuffing of schedules as possible, an even better situation is for an escort to be able to take on a request but have to push back the time of completion of later tasks without forcing any late departures. 因为我们想要尽可能少的调度洗牌，一个更好的情况是，一个托运者接受一个请求，但是不得不后推后来任务的完成时间，而不用强
制任何的迟的离港。 An escort who meets this requirement is in group O3. 一个满足这个要求的托运者放到03组里。 Finally, the ideal situation is when the dispatcher can assign a request to an escort without rescheduling that escort’s later tasks. 最后，理想的情况就是当分配者分配一个请求给一个托运者，而不重新分配托运者稍后的任务。 If the next task is to start at time ts at location s, then escort e must be able to complete the request with enough time to go from d to s by ts, 如果下一个任务在ts时间开始，在地点s，那么托运者e必须能够在足够的时间内完成请求。（在ts时间内从d走到s）
t + δ < t . e ds s
An escort who meets this requirement is in group O4 . 满足这个要求的托运者分到组04中。 The dispatcher determines the most optimal group that is not empty and chooses an escort in it for the request whose previous task brings that escort closest to the arrival location of the passenger in the new request. 分配者决定最优的组，这个组不是空的，并且在中间为请求选择一个托运者，它的前一个任务使他离新请求的顾客到达的地点最接近
。 If a new request bumps out one or more queued requests, they must be rescheduled before the dispatcher advances to to the next request on the list. 如果一个新的请求碰上一个以上的排队的请求，在调度者处理列表上的下一个请求之前，他们必须被重新调度。
If a request cannot be scheduled, every escort will either be busy with an- other request or will be too far away to arrive in time. 如果一个请求不能被调度，每一个托运者将会忙于另一个请求或者不能及时到达。 In such a case, the passenger must be scheduled for a later ?ight and/or compensated for miss- ing the ?ight, and the situation falls out of the algorithm. 这种情况下，顾客必须被调度到另一个航班，或者因延误航班而接受补偿，这个情况脱离了算法。
Simulation Algorithm 模拟算法
We envision the problem as a temporal “packing” problem—the dispatcher must fit as many tasks onto the escorts’ schedules as possible. 我们把这个问题看做一个时间包装问题-分配者必须把尽可能多的任务添加到托运者调度中。
Algorithm : MainSimulation(D, R, NE) 算法：
create escort task array E I = FindIndexUnfulfilledRequest(R) while I > 0 ? O = MakeOptimalityMat(D, RI , E) ? ? ? comment: Now execute request do ? (R, E) = ExecuteRequest(D, R, E, I, O) ? ? I = FindIndexUnfulfilledRequest(R) totalmissed = Sum(Rmissed ?ights)
totaldelay = Sum(delaytime) return (totalmissed, totaldelay)
MainSimulation() handles the entire simulation. 这个函数处理了整个的模拟。 We input the shortest- travel-time matrix D, list of requests R, and number of escorts NE . 我们输入最短旅行时间矩阵D，列出请求R，托运者的数量NE。 Entry Ej of the task array is escort j’s task schedule. 任务阵列的Ej条目是托运者j的任务调度。 The two main routines within the simulation are MakeOptimalityMat() and ExecuteRequest(). 模拟中两个主要的方法是MakeOptimalityMat() 和 ExecuteRequest()。 Together, they determine which escort is most suited to be assigned the request at hand, and how the current schedule of the escort will be changed to accommodate the new request. 总共，他们决定了哪个托运者更适合被分配给手上将要被分配的请求，以及当前托运者的调度如何被改变来适应新的请求。 MakeOptimalityMat() makes a NE ×4 matrix, with row j representing the inclusion in or exclusion from the optimality groups of escort ej . MakeOptimalityMat()创造了一个NE*4的矩阵，行j代表了ej托运者从最优托运者组中列入或者排除。
Each row of MakeOptimalityMat() is generated by OptimalityCheck(), shown on the next page. MakeOptimalityMat()的每一行是通过OptimalityCheck()来产生的，在下一页中会展现。 For each request, OptimalityCheck() assigns escorts into optimality groups. 对于每一个请求，OptimalityCheck()分配托运者到最优组中。 OptimalityCheck() creates a row of an optimality matrix O, with entry Oi,j denoting whether escort i is group j-optimal—that is, i is in group j . OptimalityCheck()造一个最优矩阵O的一行，条目oi，j表示了托运i是否在groupj里。 Finally, ExecuteRequest() (shown on p. 401) assigns an escort, if possible. 最后ExecuteRequest()分配一个托运者，如果可能的话。 As the groups descend in optimality, the dispatcher undertakes more and more actions in attempting to assign the request at hand. 随着最优组的产生，分配者承担了更多分配手上现有请求的动作。
Algorithm : OptimalityCheck(D, R , e ) I j
initialize Oj = (0,0,0,0) if Escort j is Group 1 Optimal (can ful?ll RI with delay) then Oj,1 = 1 if Escort j is Group 2 Optimal(can ful?ll RI w/o delay) then Oj,2 = 1 if Escort j is Group 3 Optimal(can ful?ll RI w/o removing tasks) then Oj,3 = 1 if Escort j is Group 4 Optimal(can ful?ll RI w/o shifting tasks) then Oj,4 = 1 return (Oj )
Deployment Plan 布置计划
We measure costs in United States Dollars (USD). There are two cost cate- gories: 我们测算了美元费用，有两个费用范畴。
? costs dependent on the number of wheelchair/escort pairs, speci?cally, wheelchair maintenance/storage costs and escorts’ wages, and 依赖轮椅托运者配对的费用，特别的轮椅维护和存储费用以及托运者的薪水，还有
? costs dependent on the number of delayed ?ights and passengers who miss their ?ights. 依赖延误航班和乘客错过了自己的飞机的次数的费用。
All wheelchair and escort costs are considered ?xed throughout the (one-day) duration of a simulation. 所有的轮椅和托运者费用在模拟的一整天中被认为是固定的。 In our cost function, NE is the number of escorts, R is the daily request list, D is the airport layout, X is the number of missed ?ights, and Y is total amount of time that ?ights that must be held at the gate due to late passengers. The objective function is thus: 在我们的费用函数中，NE是托运者数量，R是每天的请求列表，D是飞机场的布局，X是错过航班的数量，Y是飞机在登机门等待迟到乘
客的总时间。函数的目标是：
[X, Y ] = MainSimulation(D, R, NE ),
C(X, Y ) = Cost?xed + CostmissX + CostdelayedY
The average cost per hour of a ?ight held at the gate is assumed to be $1,018, the average cost in 1986 [Nathan L. Kleinman, Stacy D. Hill 1998] adjusted for in?ation [Friedman 2006]. 航班在登机门每小时的平均滞留费用假定为1，018美元，1986年去除通胀后的平均费用。 The cost of missing a ?ight is $500, the price of ticket reimbursement and/or lodging if necessary. Our ?xed costs include the maintenance costs of the wheelchairs and wages of escorts. 错过航班的费用是500美元，偿还的机票价格以及必要的食宿。我们的固定费用包括了轮椅的维护费以及托运者的薪水。 We assume that wheelchairs cost $130/yr/chair [Alexander 2006] to maintain, store, and replace as needed, and that escort wages are $10/h. [Avjobs.com 2006]. 我们假定轮椅维护，存储以及必须得更换费用为每年130美元每只，托运者的薪水是10美元每小时。 The
Algorithm : ExecuteRequest(D, R, E, I, M) 算法：
if column 4 of O contains a 1 如果o的第4列存在1 ? ? Find escort with closest previous task e 寻找前一个任务最近的托运者e ? ? then Insert task into schedule of e 把任务插入e的调度。 ? Mark request RI as ful?lled 请求ri标记为为满足的 else if column 3 of O contains a 1 如果o的第3列存在1 ? ? Find escort with closest previous task e 寻找前一个任务最近的托运者e ? ? ? ? Determine insertion spot s for task 确定任务的插入点s ? ? ? then Move jobs after s back farthest possible Insert task into schedule of e? 把s之后的作业尽可能的移到后边 把任务插入e的调度 ? ? ? ? Mark request R as ful?lled 把r标记为实现 ? I ? ? Move jobs after s forward farthest possible 把s后的作业尽可能的向前移动 else if column 2 of O contains a 1 如果第2列存在1 ? ? Find escort with closest previous task e 寻找前一个任务最近的托运者e ? ? ? ? Determine insertion spot s for task 确定任务的插入点s ? ? ? ? Move jobs after s back farthest possible 把s之后的作业尽可能的移到后边 ? ? ? ? Insert task into schedule of e 把任务插入e的调度 then Mark request R as ful?lled 把r标记为实现 ? I ? ? ? Remove overlapping tasks in schedule 移除队列中重叠的任务 ? ? ? ? Mark corresponding requests as unful?lled 标记相关请求为未满足 ? ? ? Move remaining jobs after s forward farthest possible 把s后的剩余工作向前移动 else if column 1 of O contains a 1 如果第1列有1
? ? Find escort with closest previous task e 寻找前一个任务最近的托运者e ? ? ? ? Determine insertion spot s with minimum delay 确定最小延误的插入点s ? ? ? ? Move jobs after s back farthest possible s后的作业尽可能的向后移 ? ? ? ? ? Insert task into schedule of e 把任务插入e的调度 ? then Mark request RI as ful?lled 标记ri为满足 ? ? Remove overlapping tasks in schedule 删除调度中的重叠任务 ? ? ? ? Mark corresponding requests as unful?lled 标记相关请求为未满足 ? ? ? ? Move remaining jobs after s forward farthest possible 进可能的向前移动s后的剩余工作 ? ? ? Log delay of RI 记录ri为延误 else Mark task as ful?lled 标记任务为满足
Log RI as missed ?ight 记录ri为错过航班 return (E, R) 返回
Cost?xed term is thus given by 固定项目的费用 Cost?xed = 10 + 130 HNE
365 ×24
where H is the simulation period in hours. h是模拟期的小时数。
Results and Analysis 结果和分析
Test Protocol 测试协议
Before delving into the results of test simulations, we clarify certain proto- cols used. 深入模拟测试的结果之前，我们弄清楚使用过的特定协议。
? Each data point on every plot represents 10 trials. 每个情节的每一个数据点代表10次尝试。
? Error bars are one standard deviation. 错误栏是一个标准偏差
? Half of all requests are known ahead of passenger arrival (typical). 所有的请求中有一半会在乘客到达之前被了解（典型）。
Optimizing Schedules 优化调度
We demonstrate the effectiveness of adaptive scheduling, that is, the allow- ing of escorts to be placed in optimality groups 1, 2, and 3. 我们模拟自适应调度的效率，也就是，允许托运者被放到1，2，3最优组中。 We simulated a small one-concourse setting with moderate traf?c (15,000 passengers/day) and successively removed placing escorts in optimality groups 1, 2, and 3, in that order. 我们模拟一个小的普通吞吐量（15，000乘客每天）的一个大厅的情况，连续移除的把托运者放入最优组1，2，3中，按照顺序。 In other words, the simplest algorithm is for a request to be missed if no escort is in O4, the next simplest algorithm is for a request to be missed if no escort is in O or O , etc. These simulations were carried out assuming that 4 3 也就是说，最简单的算法是，如果没有托运者在04，一个请求将会被错过，第二简单的算法是，如果没有托运者在o3或o4，一个请求
也会被错过。这种模拟的运行是假定了1.2%的乘客请求轮椅服务。
1.2% of the passengers require wheelchair assistance. There are large gains from shifting around existing tasks in an escort’s sched- ule, that is, the inclusion of group O3. The effect is substantial—we avoid hiring ?ve or six escorts, resulting in savings of about $1,000/d (Figure 1). 在托运者的调度中现存任务中的转移是有很大的好处的，也就是，03组的列入。效果很大-避免了雇佣5或6个托运者，导致大约每天1
，000美元的节省。 Savings would increase with passenger traf?c and airport size. 节省会随着乘客交通以及飞机场尺寸而增加。 With several airports, Epsilon Airlines may see total savings on the order of $10,000/d, merely by adopting our adaptive scheduling. Epsilon航空公司有几个飞机场，他们会看到每天10，000每天的节省，仅仅通过采纳我们的自适应调度。
Performance/Sensitivity across Concourses 大厅之间的效率
We use Chicago O’Hare terminals as test locations for examining perfor- mance in different-sized settings. 我们使用ChicagoO'hare机场作为实验地点，来检查不同尺寸机场下的效果。 We ran simulations for one-, two- and four- concourse settings, corresponding to Figures 2—4. 我们在一个大厅两个大厅四个大厅的情况下模拟。 Each set of simulations spans three levels of terminal traf?c, assuming that 0.6% of passengers require wheelchair assistance. 每一个情况跨越三个交通等级，假设0.6%的乘客需要轮椅服务。 Comparing costs vs. number of escorts, we observe
A Simulation-Driven Approach 407
x 104 Scheduling Comparison (15000 passengers/day) 8 O1,O2,O3,O4 7 O2,O3,O4 O3,O4 O4 6 ) D S U 5 ( y a D 4 r e P t 3 s o C 2
1
0 0 5 10 15 20 Number of Escorts
Figure 1. Comparison of scheduling methods.
an increase in the optimal number of escorts roughly proportional to the in- crease in the number of concourses. 最优数量的托运者的增加与大厅数量的增加成正比。 Furthermore, as airport traf?c increases, we generally see a rise in the number of escorts needed to maintain optimal cost. 而且，随着机场交通增加，我们看到维持最优费用所需的托运者数量会增加。 Figure 4 shows that in a single-concourse setting, increased traf?c density barely increases the optimal number of escorts, whereas Figures 3 and 4 show substantial increases in escort demand within the two- and four-concourse set- tings, due to longer travel times between gates. 在一个大厅的情况下，交通密度的增加仅仅增加了托运者的最优数量，而在两个和四个大厅的情况下，托运者数量会增加，由于两个
门之间的托运时间增加造成的。
Performance/Sensitivity across Airports 机场上的效率和灵敏度 Our algorithm has the ?exibility to address any airport con?guration, since we use satellite images of an airport to convert it to its node-edge representation. 我们的算法对于处理任何一个机场情况是有弹性的，因为我们试用了一个机场的卫星图像，把它转化成为一个点边图表示。 We perform a comparison analysis on three airports. 在三个机场中做一个比较分析。 We examine two- concourse sections from New York’s LaGuardia (LGA), Chicago O’Hare (ORD), and Dallas/Fort Worth (DFW) airports, at two separate traf?c levels, assum- ing that 1.2% of passengers require wheelchair assistance. 考察两个大厅的机场，纽约的lga，芝加哥的ord，达拉斯的dfw，两个不同的交通等级，假定1.2%的乘客需要协助。 From the satellite images, we hypothesized that DFW would fare the worst, due to passengers having to walk from one side of the circular terminals to the other (almost a mile), and that Chicago O’Hare would perform best, since it has a more compact layout, with passengers able to cross through a triangular intersection among concourses. 从卫星图形上看，我们假设dfw的费用最贵，因为乘客不得不从环形飞机场的一边走到另一边（差不多一公里） 芝加哥的ord最好，因为他有一个更紧凑的布局，乘客能够在大厅之间通过一个三角形的路口穿越。 However, Figure 5 shows that algorithm performance is statistically equiv- alent, despite different airport geometries, over the wide range of numbers of passengers per day, and over 10 averaged trials for each data point. 但是，算法效率是静态的等效的，尽管不同的机场几何上不同，每天乘客的数量也分布广泛，每个数据点有超过10个平均实验。 x 104 O’Hare Terminal 3 West Concourse Only O’Hare Terminal 3
West Concourse Only 3 0.7 8000 passengers/day
8000 passengers/day 12000 passengers/day g
12000 passengers/day 2.5 n 0.6 i 17000 passengers/day t
17000 passengers/day r o c s ) 2 E 0.5 D t n S e U p ( S y 1.5 0.4 a e D m i r T e 1 l 0.3 P a t t o s T o C f o 0.5 0.2 n o i t c a 0 r 0.1 F
0.5 0 0 2 4 6 8 10 12 0 2 4 6
8 10 12 Number of Escorts Number of
Escorts
Figure 2. Chicago O’Hare Terminal 3 West Concourse only.
4 O’Hare Terminal 2 O’Hare
Terminal 2 x 10 3 0.7 10000 passengers/day
10000 passengers/day 30000 passengers/day g
30000 passengers/day n 0.6 i 2.5 50000 passengers/day t
50000 passengers/day r o c s ) E 0.5 D t 2 n S e U p ( S y 0.4 a e D 1.5 m i r T e l 0.3 P a t t o s T o 1 f C o 0.2 n o i t c 0.5 a r 0.1 F
0 0 0 2 4 6 8 10 12 14 0 2 4 6
8 10 12 14 Number of Escorts Number of
Escorts
Figure 3. Chicago O’Hare Terminal 2.
A Simulation-Driven Approach
409
4 O’Hare Terminal 3 O’Hare
Terminal 3 x 10 8 0.7 35000 passengers/day 7 70000 passengers/day g n 0.65 i 90000 passengers/day t r o c 6 s ) E 0.6 D t n S e U 5 p ( S y 0.55 a e D 4 m i r T e l 0.5 P a t t 3 o s T o C f o 0.45 2 n o i t c 35000 passengers/day a r 0.4 1 F 70000 passengers/day 90000 passengers/day 0 0.35 4 6 8 10 12 14 16 18 4 6 8 10
12 14 16 18 Number of Escorts Number of
Escorts
Figure 4. Chicago O’Hare Terminal 3.
Our al- gorithm performs equally well regardless of airport con?guration, though for higher traf?c levels we might see differences among airport geometries.
x 104 Airport Comparison (10000 passengers/day) x 104 Airport Comparison (30000
passengers/day) 4 9 New York LGA
New York LGA 3.5 D/FW 8
D/FW Chicago ORD
Chicago ORD 7 3 ) ) D D 6 S S U 2.5 U ( ( y y 5 a a D 2 D r r e e 4 P P t 1.5 t s s o o 3 C C 1 2
0.5 1
0 0 0 2 4 6 8 10 4 6 8 10 12
14 16 Number of Escorts Number of Escorts
Figure 5. Comparison of algorithm performance at different airports.
Predicting For An Aging Population 预测老龄化问题
The demand for wheelchair assistance will increase in the future. 未来对于轮椅服务的需求会增长。 The ques- tion is, What does this entail? 问题是，这意味着什么？ Should an increase of 10% in the requests per capita be treated the same as a 10% increase in total volume of passengers? 请求者10%的增长被认为与总的乘客10%的增长是一样的嘛？ The answer from our simulations appears to be that it should be treated as more. 答案从我们的模拟中看起来应该被更多而考虑。 A 10% percent increase in population would increase the number of
scheduled ?ights per day; a 10% increase in requests per capita would not. 10%的人口增长将会增加每天被调度的航班；请求10%的增加则不会。 In other words, as the average passenger ages, the result is not just more requests but more requests per plane. 换句话说，乘客平均的年龄增长，结果并不只是更多的请求，还有每个飞机更多的请求。 We ran two series of simulations for a two-concourse airport. 我们在一个两个大厅的飞机场作模拟。
? We increased the number of passengers (and thus correspondingly the num- ber of ?ights) from 33,000 to 42,000. 我们增加了乘客数量（相应的航班数量）从33，000到42，000
? We held the number of passengers constant at 30,000 and increased the request percentage from 1.32% to 1.68%. 我们让乘客的数量保持稳定在30，000并且增加请求的比例从1.32%改为1.68%
In each series, the number of requests is the same, but the average minimum cost is greater when the percentage increases (Figure 6). 在每一个系列中，请求的数量是相同的，但是平均最小费用更大，当比例增加时。
Increasing Requests per Capita versus Increasing Population 3300 Constant Number of Flights 3200 Proportionally Increasing Flights
3100
3000 t s o 2900 C t s e 2800 B
2700
2600
2500
2400 396 432 468 504 Number of Requests
Figure 6. Comparison of increase in requests.
Conclusions 结论
A weakness of our approach is that we do not speci?cally optimize towards minimizing damages. 我们方法的弱点是，我们不能最小化损失。 For example, an escort may have ?ve short tasks (in terms of time from arrival gate to departure gate) queued, when a lengthy request is received. 比如，托运者可能有更短的任务（从到达门到里开门的时间）在队列中，当一个长的请求接收到时。 The dispatcher may end up striking three or four tasks from the escort’s schedule in order to ful?ll the one new task—but the removed tasks’ passengers may miss their departure times. 分配者移除托运者的调度中的3个或4个任务，目的是完成新的任务-但是溢出的任务的乘客可能会错过他们的登机时间。 We sacrifice many passengers for the sake of one. 我们为了这个原因牺牲了很多的乘客。 However, this situation is rare, since we try to minimize the chance of any passenger missing his/her ?ight. 但是，这个情况是少见的，因为我们尝试最小化乘客错过航班的可能性。 If this type of situation is
encountered frequently, then we have probably not optimized the number of escorts. 如果这种情况经常碰到，那么我们可能不能最优化托运者的数量。 Our method also assumes no delayed arrivals or departure delays due to other causes. 我们的方法也假定了没有延迟的到站或者离港延误，由于其他原因。 The dispatcher has the dif?cult task of managing escorts’ schedules, but this is feasible with a computer. 分配者有安排托运者调度这样困难的任务，但是这用电脑是可行的。 These weaknesses are outweighed by the demonstrated robustness and im- provements of our approach. We have shown in a variety of settings that not only does our algorithmic approach work but it outperforms simpler algo- rithms by substantial margins. 这些弱点被展示的鲁棒性和方法的改进所抵消。我们在各种情况下展示，不知算法正常工作，而且它在大量保证金情况下超越了更简
单的算法。
References
Alexander, Richard. 2006. Lifecare planning for the BK amputee: Future med- ical costs. http://consumerlawpage.com/article/amputee.shtml.
Avjobs.com. 2006. Aviation career salary ranges. http://www.avjobs.com/ table/airsalry.asp.
City of Atlanta. 2006. Atlanta international airport ?ight information. http: //www.atlanta-airport.com.
Friedman, S. Morgan. 2006. In?ation calculator. www.westegg.com/ inflation/.
Google.com. n.d. Google maps. http://maps.google.com.
Haseltine Systems Corporation. 2006. Haseltine Systems Corporation. http: //www.haseltine.com/data.html.
Kleinman, Nathan L., Stacy D. Hill, and Victor A. Ilenda. 1998. Simulation optimization of air traf?c delay cost. In Proceedings of the 1998 Winter Simu- lation Conference, edited by D.J. Medeiros, E.F. Watson, J.S. Carson, and M.S., Manivannan, 1177–1181.
Neufville, Richard De. 1976. Airport Systems Planning. Cambridge, MA: MIT Press.
Wang, Yi. 2006. Dijkstra algorithm consistent with cyclic paths. http://www.mathworks.com/matlabcentral/fileexchange/loadFile. do?objectId=7869&objectType=file.
