基于仿真驱动的成本高效机场轮椅协助服务研究与优化资源-CSDN文库

版权申诉

调度算法

成本优化

135 浏览量 2024-11-29 12:40:51 上传评论收藏 472KB PDF 举报

资源推荐

资源详情

资源评论

A Simulation-Driven Approach For A Cost Eﬃcient Airport

Wheelchair Assistance Service

Team # 868

February 6, 2006

1 Introduction

Although roughly 0.6% of the US population is wheelchair-bound, the strain of travel is such that, according

to some estimations, more than twice that amount relies on wheelchairs in airports [5]. Even those who

have their own chairs still rely on airlines fo r assistance when making connections.

Fo r airlines to provide this service eﬀectively, they must ﬁnd a way to skirt the boundary between doing

too much and doing too little. Many factors are under the company’s control: the maintenance schedule

for the wheelchairs, the amount of seasonal hiring to meet the holiday rush, etc. Ultimately, though, two

issues have the greatest impact on the cost and eﬀectiveness of their service: how many wheelchairs they

should have, and how they should be deployed. These are the focus of this study.

If an airline has too few wheelchairs or employees to move them, they will not be able to reach all

passengers with enough time to make it to their ﬂights on time. If they delay the ﬂight for these passengers,

costs are incurred in terms of lost time. If a ﬂight must leave without a passenger who needed to be escorted,

the passenger must be reimbursed, and, if such an occurence is routine, the reputation of the company

suﬀers.

On the other hand, if an airline has grossly over-estimated the demand fo r assistance, they will lose

money spent on the wages of idle escorts and on superﬂuous wheelchairs. The cost of a wheelchair is

greater than just the initial purchase price: they must be maintained, and because space is at a premium

at an airport, the cost of storing them is also non-trivial.

In developing a method of deployment, tending to the extremes is equally ill-advised. If the escorts

had to determine their own movements about the airport, the lack of coordination would result in areas

of the airport going unattended. The ﬂuctuation of requests could be so great, though, that a plan which

gives each escort a territory could both over- and under-work escorts in diﬀerent areas.

Air travel is non-uniform to such a degree that t he proper number of escorts and wheelchairs is not

only a question of the airport but of the volume of passengers, which can vary greatly.

In this study, we present an algo rithm for the scheduling of the movement of escorts which is both

simple in implementation and eﬀective in maximizing the use of available 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.

Team # 868 Page 2 of 19

2 Methods And Assumptions

To determine an optimal scheduling and deployment plan, we propose a stochastic simulation-driven opti-

mization procedure. We partition the problem into t hree 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 wheel chair

assistance requests for a time period of one 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.

2.1 Pre-Simulation

2.1.1 Airport Layout

Airports vary enough in geometry and layout to motivate optimization on a per-airport basis. The eﬀect of

airport geometry is not immediately apparent, so the simulation is customized for the layout of a speciﬁc

airport. We r epresent an airport as a bidirectional graph, in which nodes indicate gat es, entrance/exit

points, or other places of similar interest. Edges between nodes indicate travel paths, usually through the

main hallway of a concourse. For example, Figure 1 shows the graphical representation of terminals 2 and

3 of Chicago O’Hare International Airport, constructed with the aid of a satellite image [4].

Airports are designed such tha t passengers must travel through long corridors to reach their departure

gate. As such, a typical concourse has gates located on either side of the main corridor. We assume that

the time required to travel from any gate to any gate is nontrivial; that is, even if two gates are a djacent

and on opposite sides of the main corridor, the travel time between the two gates is taken into account.

The graphical representation of t he airport is encoded in an n × n adjacency matrix, A, with entry

i,j

denoting the travel time between location i and location j. We determine travel times by ﬁguring the

actual distance divided by a walking speed of 3 miles/hour. The shortest possible t ravel times (calculated

using Dijkstra’s Algorithm [9]) from every location to every other location is referenced in matrix D, with

entry D

denoting the shortest travel time between nodes i and 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.

2.1.2 Wheelchairs And Escorts

A wheelchair and its corresponding escort are treated a s a single traveling entity. In reality, the airline

may have additional wheelchairs on hand fo r the event of a malfunction, and the cost of the additional

wheelchairs is incorpo r ated into the maintenance and storage costs of the wheelchairs in operation. The

wheelchair/escort pair will henceforth be referred to as the “escort”. The escort’s job is to travel to the

arrival gate of the passenger and transfer the passenger to the departure gate. As described above, escorts

require a constant amount o f time to move from location to location. We alter the number of escorts

needed to develop an optimal deployment plan.

An important assumption is that the number o f escorts remains constant throughout the simulation

period. In reality, escorts will rotate in shifts, but with a simulation period of one day, we assume that

escorts presently starting their shifts immediately replace the escorts ending their shifts. Similarly, during

the simulation period, we do not allow the real-time hiring or ﬁring of workers, nor the real-time buying

Team # 868 Page 3 of 19

or breaking of wheelchairs. Instead, we represent the costs associated with these actions with a sunken

cost term in the total cost function.

2.1.3 Passenger R equest List

Given a terminal, we then proceed to create a ﬂight schedule for one day at the airport. To do this, we

look at the total number o f passengers who pass through the airport in a day. We estimate the average

load of a plane to be 1 25 passengers, which we use to estimate the number of ﬂights arriving or departing

at the terminal in one day. Observation of departing ﬂight information at a busy airport [8] conﬁrms the

information in another source [7]: there is regular activity between 6 AM and 10 PM and relatively few

ﬂights at night. We therefore space our departures evenly between these times, and then perturb these

va lues by a random shift o f less than an hour, so that we are certain not to t est our algorithm against just

one schedule. Subsequently, these ﬂights are assigned to speciﬁc gates. (See Fig ure 2)

Next, we create the requests for the day. We generate the number of requests based on the total

passenger volume we are trying to mimic and the percentage of the population that requires wheelchair

assistance while traveling. For diﬀerent runs, this va lue was either 0.6% or 1.2% [5]. Each request is

assigned an a r riving ﬂight and a departing ﬂight with the a ssumption that no layover o f less than half

an hour should be attempted. We assume t hat a certain percentage of passengers have phoned the

airline ahead of time, so their request time (time of request) is set to 0. Fo r those that remain, we

generate a random request time, varying from more than ﬁve hours to a half hour. This list is then sort ed

chronologically by request time, so that when the algorithm descends the list, it mimics the dispatcher’s

receiving the requests at varying times throughout the day, including the wheelchair needs that occur with

little notiﬁcation (See Figure 3).

Diﬀerent daily scenarios may be modeled by merely altering the generation of the request list. The

request list in eﬀect models the passenger traﬃc load throughout the simulation, as it will contain 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 a irports, or yearly peak

travel periods at airports located in popular vacation destinations.

2.2 Scheduling Plan

We assume t hat each airport has escorts who can communicate with a dispatcher via a walkie-talkie, and

that the dispatcher has a schedule for each escort. For schedule for jobs in the future is mutable. When

an escort has completed one task, he calls his dispatcher to ﬁnd out his next. We assume the dispatcher

knows how long it takes an escort to get between two points x and y, which we call δ

A dispatcher receives requests at varying times throughout the day. Some requests may have been

scheduled before the day begins, others may come only just before they must be executed. Each request

contains four pieces of infor matio n: the time and location of the passenger’s arrival, t

and a, and the time

and location of his departure, t

and d. For the passenger to reach his destination in a timely fashion,

whichever escort assists him must arrive at a location by some ﬁnal time,

= t

− δ

The algorithm’s verion of “ﬁrst come, ﬁrst served” is that one task cannot replace another on a schedule

if its ﬁnal time is later. 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).

Team # 868 Page 4 of 19

To determine on whose schedule the task should be put, the dispatcher ﬁrst ﬁnds out if anyone can

complete the task in the least optimal fashion. From those who can do that, he ﬁnds those who can

complete the task in a more convenient fashion, until he determines the most optimal way in which

someone can complete the task.

The least optimal way in which a request can be fulﬁlled is for the escort to bring t he passenger to

his destination late, yet within the window, δ

, in which ﬂight is delayed. To determine if escort e can do

this, t he dispatcher looks at what location, l

, he will be at the completion of his last job before the ﬁnal

time of the request, and at what time that job will be completed, t

. We must have

+ δ

< t

+ δ

If escort e meets this requirement, then he is in the group O

The next most optimal way in which a request can be fulﬁlled is if a n escort can bring the passenger

to his destination on time, but must remove something from his schedule later. The condition for this one

is the same as above, but without the delay term:

+ δ

< t

If escort e meets this requirement, then he is in the group O

Because we want to do as little reshuﬄing of schedules as possible, the next most optimal situation is

for an escort to be able to take on a request, yet still needing to push back the time of completion of his

later tasks. The dispatcher checks to see if, assuming the request was added, the sequence of travel times

and service times tha t would result has no late departures. If an escort meets this requirement, then he is

in the group O

Finally, the most ideal situation is when the dispatcher can assign a request to an escort without

rescheduling his later tasks. If his next task is to start at time t

at location s, then escort e must be able

to complete the request with enough time to go from d to s by t

+ δ

< t

If an escort meets this requirement, then he is in the group O

Once t he dispatcher has determined the escorts that fall under each category, he determines the most

optimal gro up that is not empty, and chooses one of them to schedule the request. This decision is made

by giving the request to the escort whose previous task brings him closest to the arrival location of the

passenger making the new request. If a new request bumps out one or more queued requests, they must

be rescheduled before a dvancing to the next request on the list. If a r equest cannot be scheduled, it means

that every escort will either be busy with another request, or will be too far away to arrive in time. In

such a case, the passenger must be reimbursed for missing his ﬂight, or scheduled for a later ﬂight. We

assume that such transactions are beyond the scope of the dispatcher’s duties, so the situation falls out of

the algorithm. Continuing in this fashion, the dispatcher will read and a ssign requests until all requests

are properly fulﬁlled.

In scheduling requests, the alg orithm a t t empts to minimize the total time during which the escorts are

stationary. As a simple example, the dispatcher assigns a request received at the beginning of the day to

an escort. Before the the escort can execute t hat task, a new unpredicted request from a passenger with

earlier departure time is received. To minimize idle time, the dispatch will assign the escort to meet t he

second passenger and proceed to the departure gate, as long as this task does not invalidate the completion

of the ﬁrst task.

剩余18页未读，继续阅读

评论收藏

内容反馈

版权申诉

pk_xz123456

粉丝: 2284
资源: 2353

基于仿真驱动的成本高效机场轮椅协助服务研究与优化

论文研究-基于仿真模型的排队规则遗传优化算法研究.pdf

基于Matlab的6自由度机械手臂的研究与仿真

基于Matlab的机器人单关节驱动系统仿真设计与分析.pdf

基于仿真的飞机导管自动化生产线规划设计与优化.rar

基于WinCC组态软件的加热炉炉温优化与仿真研究

论文研究-雷达系统仿真中基于消息驱动的通信服务模型之研究.pdf

分布式驱动电动汽车转弯转矩优化方法与仿真验证.pdf

航空公司残疾人服务轮椅与护工调度成本最小化算法研究

基于python的机场调度模拟仿真系统源码+说明.zip

基于Flexsim的服装企业配送中心布局仿真优化.doc

simjava2离散事件驱动仿真

基于排队论和Anylogic仿真的车站进站排队优化.pdf

基于Matlab的螺栓旋拧机器人驱动系统仿真研究.pdf

基于串联弹性驱动器的柔顺机械臂设计与仿真.pdf

基于 OPNET 的单工无线通信仿真研究

基于高斯过程的Bayesian贝叶斯全局优化matlab仿真+代码仿真操作视频

基于遗传优化的微电网调度优化matlab仿真+仿真录像

基于MATLAB_Simulink软件汽车感应电机驱动控制系统的仿真研究.pdf

基于机器人的仿真研究

瑞萨EZ-CUBE仿真器驱动

仿真驱动的5G射频MEMS滤波器优化流程

基于MATLAB_Simulink的欠驱动机器人仿真实验.pdf

XDS100V2 USB仿真器驱动程序

MATLAB与HFSS联合建模与仿真优化详细介绍

最新资源