基于 GSAA 的停机位指派优化问题的研究
基于GSAA的停机位指派优化问题的研究
鞠姝妹1，许俐
（南京航空航天大学民航学院， 南京 210016）
摘 要：停机位的合理指派是机场地面作业中的一项核心任务，对减少枢纽机场航班中转时间起着重要作用，但是停机位指派问题是NP难问题，模型和算法都比较复杂。本文建立了以旅客满意度为优化目标的数学模型，并设计了一种贪婪模拟退火算法（GSAA），以求解枢纽机场的停机位指派问题。该算法首先根据贪婪算法FCFS 准则使“丢失”的航班数最少得到模拟退火算法的初始解，然后运用经典模拟退火算法求解出最优指派结果。数值仿真证明了模型和算法的有效性。 关键词：枢纽机场；停机位指派；旅客满意度；贪婪模拟退火算法
Airport Gate Assignment Problem based on GSAA
JU Shumei, XU Li
(School of Civil Aviation，Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
Abstract: Airport gate assignment is a key task among the airport ground work which is important to reduce transfer time in hub airports. However, the gate assignment problem (GAP) is an NP-hard problem, its models and algorithms are complex. This paper proposed a model and a new greedy simulated annealing algorithm (GSAA) to resolve the GAP. The initial solution of the proposed algorithm is obtained through FCFS criterion of greedy method to minimize the “dropping” flights, and then the optimal solution is got by the traditional simulated annealing algorithm. Simulation result shows the validity of the model and the algorithm.
Key words: hub airport; gate assignment problem; the degree of passenger satisfaction; greedy simulated annealing algorithm
1 引言
停机位分配是指，在考虑机型大小、停机位大小、航班时刻等因素的情况下，在一定时限范围内，由机场生产指挥中心为到港和离港航班指定适宜的登机口，保证航班正常不延误，为旅客上下航班提供登机门[1]。针对停机位分配问题，目前国外学者已经提出了多种分析方法，如专家系统、分支定界算法以及结合单纯型法和分支定界算法的优点提出的解决策略。此外还有一些基于数学模型的方法，它们的客观作用通常是减少旅客的步行距离、减少未被利用的停机位数量、减少使用停机位的时间段等问题。国内针对这方面的研究都相对较晚。
本文建立了以旅客满意度为优化目标的数学模型并设计了一种贪婪模拟退火算法（GSAA）以求解枢纽机场的停机位指派问题。
2 枢纽机场停机位指派模型描述
2.1 假设条件
在建立模型之前，首先引进三个假设条件：
（1）容量满足假设。机场的航班量和时间分布保持在机场容量许可范围内，即在任意时
基金项目：民航总局软科学基金项目（MHRD0622）
作者简介：鞠姝妹（1984－），女，江苏，南京航空航天大学硕士研究生，从事交通运输规划与管理研究。
刻，总可以为任一航班指派一个停机位，尽管不是最优但一定是可行的。
（2）信息完备假设。在某一个工作日开始之前，GAP 决策所必需的航班计划、机场资源等信息是完备的和已知的。
（3）虚拟中转假设。引进虚拟航班和虚拟停机位，认为以该机场为始发地的旅客，是从虚拟航班上中转而来；以该机场为目的地的旅客，是中转到虚拟航班去。这样，将出发旅客、到达旅客全部假设成中转旅客，将问题简化。
2.2 数据定义
M ：机场停机位集合，M >0，且包含一个虚拟停机位，记做停机位0。
kl d ：从停机位k 到停机位l 的距离。0l d 表示始发旅客从安检口到停机位l 的距离，0l d 表
示到达旅客从停机位L 到行礼提取处的距离。并且假设是相等的。
N ：当日航班集合，N >0，且包含一个虚拟航班，记做航班0，用以表示机场本身。 ik P ：航班i 的机型是否与机位k 匹配，值为1表示匹配。
ij f ：从进港航班i 到出港航班j 的转机旅客人数。0i f 表示进港航班i 中以本机场为目的
地的旅客人数，oi f 表示从本机场出发，乘坐出港航班i 的人数。|0ij
i j f ==。
2.3 构建目标函数
以旅客的角度优化停机位配置，构建服务质量目标函数，指标为旅客转机所需要移动的距离[8]
。枢纽机场停机位分配问题的目标函数表示为：
,,min
ij kl ik jl i j N k l M
f d y y φ∈∈=∑∑
（1）
其中i≠j ，k ≠l,
1 i k 0 ik y ?=??（当且仅当航班被分配到停机位时）（否则）
2.4 约束函数
（1）每个航班只能分配一个机位：
1,ik
k G
y
i N ∈=?∈∑ （2）
（2）每个机位一次只能指派给一架飞机，即每个航班在同一停机位上，最多只有一个直接相邻
的后继航班，且最多只有一个直接前驱航班：
,,ik ijk
j N
y z
i N k M ∈=?∈?∈∑ （3） ,,jk ijk
i N
y z
i N k M ∈=
?∈?∈∑ （4）
其中，
1 0 ,ijk i j k i j z ?=??
（当且仅当航班和航班被分配到停机位而且航班是航班的直接前驱航班）（否则）
（3）停机位只能停放与其匹配的机型的飞机
1,,ik P i N k M =?∈?∈ （5）
3
算法设计
贪婪模拟退火算法（Greedy Simulated Annealing Algorithm，GSAA）分为两个阶段：贪婪算法阶段和模拟退火阶段。主要思想是：首先根据航班时刻表，并且按照“先到先服务”原则对航班进行机位分配，将得到的初步分配结果作为模拟退火算法的初始解，并用标准搜索禁忌算法（SAA）进行进一步优化，最终得到一个最优的分配结果。
要满足模型的第一个假设，即容量满足假设，必须用贪婪法进行第一次分配，贪婪算法为利用计算机进行停机位自动分配并优化停机位结果提供了一种可行手段，可以尽量减少使用远机坪的几率和减少延误的航班，使未能分配到停机位的航班数目最少，提高近机位的使用率。第二次分配从提高旅客服务质量角度构建目标函数对分配方案进一步优化。算法具体步骤如下： （1）贪婪算法阶段
该算法必须满足：①同一时间内一个机位只能分配给一个航班使用；②每个航班只能分配一个机位；③航班与所分配的机位相匹配。
设一段时间内所有待分配的航班集合为{1,2,...,}j F F j n ==（n 为待分配的航班总数），可用于停放航班的机位集合为{1,2,...,}i G G i m ==（m 为停机位总数），每一个航班j F 均有固定的使用机位的开始时间j
B T 和结束时间j
E T ，记为(,)j
j
j B E F T T =。Flt (j) =i , i=1,2,…,m ,表示航班j
F 分配给机位i
G 。
设处于待命状态的机位集合为{1,2,...,,}free i free free G G i m m m ==≤，其中free m 表示处于空闲状态的机位数。对于每个空闲的机位free i G G ∈，根据其被使用的上一个航班结束使用时刻的先后顺序定义一个对应于该机位的标号函数Pr ()o i ，Pr ()1,2,...,free o i m =，算法中根据Pr ()o i 的值决定机位i G 参与下一个航班分配的优先顺序。 算法流程如下： Step1：将所有的到达航班和出发航班按其发生时间的先后重新排序，得到在本时间段的事
件集合{1,2,...,2}k Z Z k n ==，当到达与出发同时发生时，总是安排出发事件在前。
Counter 记录“丢失”的航班数量，赋初值Counter＝0。
Step2：当航班j F 为出发航班时，k Z 为出发事件，则1fre e fre e m m =+, {()}free free i G G G i Flt j =+=,
(())free Pro Flt j m =；当航班j F 为到达航班时，k Z 为到达事件，则找出一个fre e l G G ∈，
使满足1lj P =，Pr ()min{Pr ()}free i o l o i G G =∈。如果l G 存在，则赋值()l F lt j G =，1fre e free m m =?，{}free free l G G G =?，P r ()P r ()1oi oi =?；否则()F lt j A p ro n =，Counter=Counter+1。
Step3：1k k =+。
Step4：如果k N ≤，转Step2；否则停止计算，输出(),1,2,...,Flt j j n =和Counter，并转模
拟退火阶段。
（2）模拟退火阶段
首先介绍三种邻域搜索方式：
z 插入式移动（Insert Move ）：将一个航班从一个机位移动到另一个机位，即
(,)(,)i k i l →。
z 区间交换移动（Interval Exchange Move）：将两个不同机位上的两个航班区间交换。
一个航班区间可以包含一个或多个航班，即(,,)(,,)a b k c d l ?，表示将k 机位上航班a, b 之间的航班段与l 机位上航班c, d 之间的航班段交换。 z 远机位交换（Apron Exchange Move）：将分配在远机位的某个航班（在标号算法中“丢
失”的航班）与分配到机位的航班进行交换，即(,)(,)i Apron j k ?。
算法流程如下：
Step1：初始化。确定冷却进度表参数α=0.97，初温T 0 ＝300，i =0，给定循环次数R。
利用标号阶段的指派结果作为SAA 的初始解S 0，目标函数值min ，令r =0。
Step2：新解的产生。由三种邻域搜索方式建立备选列表，备选列表用来预先确定移动的
范围，例如在移动(,)(,)i k i l →中，假设航班i 要插入到航班p 和q 之间使用的停机位l ，在式（2～5）的条件下，根据所有能让航班i 插入的停机位建立备选列表，然后进行移动，计算新解的目标函数值，记为mini 。
4
算例分析
以浦东机场某一天具体航班时刻表为例，在10:00～14:00这个时段内空闲的7个停机位
对18个即将到来的航班（一个航班波）按照上述算法进行分配。航班开始使用机位时刻TB j ，结束时刻TE j ，机位与航班的匹配参数ij P 见表1；从各航班上中转的旅客人数见表2；各机位之间的距离见表3（假设远机位到各机位的距离为一个稍大的值1000）。
表1 机位与航班的匹配特性
航班－机位匹配特性（Pij ） 航班（Fj） 开始时刻（TBj） 结束时刻（TEj）
航班机型（TFj）
G1G2G3 G4 G5 G6 G7F1 1000 1100 B737 111 1 1 0 0F2 1000 1055 B737 111 1 1 0 0F3 1000 1100 A320 010 1 1 1 1F4 1010 1105 MD11 111 1 0 1 1F5 1025 1135 B767 1110 0 0 0F6 1030 1120 A320 010 1 1 1 1F7 1105 1155 B737 111 1 1 0 0F8 1120 1220 B747 1100 0 0 0F9 1125 1205 A319 0110 1 1 1F10 1130 1220 B737 111 1 1 0 0F11 1135 1235 B757 001 1 1 1 1F12 1155 1300 A320 010 1 1 1 1F13 1200 1250 A330 110 1 0 1 1F14 1210 1340 A340 1100 0 1 0F15 1215 1305 B737 111 1 1 0 0F16 1240 1340 B747 1100 0 0 0F17 1245 1335 B737 111 1 1 0 0F18
1310
1400
B737
1
1
1
1
1
表2 各航班上旅客人数
旅客人数
航班号
0 1 2 3 4 5 67891011121314 15 16 17 18
0 0 25 1833 18 22 243242141227203330 15 25 16 21
1 66 0 0 0 0 0 001633263411916 1
2 0 0 0
2 5
3 0 0 0 0 0 0332311152016000 0 0 0
3 58 0 0 0 0 0 002611241922000 0 0 0
4 133 0 0 0 0 0 004531151419000 0 0 0
5 102 0 0 0 0 0 00000003531 2
6 0 0 0
6 84 0 0 0 0 0 0000262213000 0 0 0
7 79 0 0 0 0 0 00000005532 24 0 0 0
8 156 0 0 0 0 0 0000000000 42 33 29
9 96 0 0 0 0 0 0000000000 33 21 0
10 76 0 0 0 0 0 0000000000 22 16 12
11 122 0 0 0 0 0 0000000000 0 0 36
12 91 0 0 0 0 0 0000000000 0 0 0
13 231 0 0 0 0 0 0000000000 0 0 41
14 211 0 0 0 0 0 0000000000 0 0 0
15 112 0 0 0 0 0 0000000000 0 0 0
16 194 0 0 0 0 0 0000000000 0 0 0
17 109 0 0 0 0 0 0000000000 0 0 0
18 97 0 0 0 0 0 0000000000 0 0 0
表3 各机位间的距离
各机位间的距离
机位编号
0 1 2 3 4 5 6 7 Apron
0 0 120 60 45 88 40 57 128 1000
1 120 0 75 150 225 300 375 450 1000
2 60 50 0 75 150 225 300 375 1000
3 45 150 75 0 75 150 225 300 1000
4 88 22
5 150 75 0 75 150 225 1000
5 40 300 225 150 75 0 75 150 1000
6 5
7 375 300 225 150 75 0 75 1000
7 128 450 375 300 225 150 75 0 1000 Apron 1000 1000 1000 1000 1000 1000 1000 1000 1000 两种算法的程序是在MATLAB 6.5环境下编程实现的，贪婪算法得到的初始解为Flt(1)=Flt(16)=1，Flt(2)=Flt(7)=Flt(13)=Flt(18)=2，Flt(4)=Flt(15)=3，Flt(3)=Flt(10)=Flt(17)=4，Flt(6)=Flt(12)=5，Flt(9)=Flt(14)=6，Flt(11)=7，Flt(5)为“丢失”的航班，即分配到远机位的航班，其CPU平均运算时间是0.047秒。此时目标函数值为194206（m），但并不是最优结果，用模拟退火算法对其进行二次优化最终分配结果如表4，目标函数值提高了2.80％。
表4 最终机位分配
机位
1 2 3 4 5 6 7 Apron
F1 F4 F2 F6 F3 F9 F11 F5 F8 F13 F7 F10 F12 F14
F16 F18 F15 F17
通过改变外循环次数研究了GSAA和典型SAA算法对停机位指派模型的求解效率，其中典
型SAA的初始解是随机的，两种算法的程序是在MATLAB 6.5环境下编程实现的，收敛性见图1和图2。从图1可以看出，贪婪模拟退火算法在迭代次数达到500次，CPU运算时间达到18.453秒之前，该算法具有较高的向模型最优解收敛的速度，目标函数值改善约2%。18.453秒之后，收敛速度明显下降，目标函数值改善仅有0.6％。而从图2中可以看出，典型模拟退火算法在迭代次数达到1400次，CPU运算时间达到56.891秒之前具有较高的向模型最优解收敛的速度，目标函数值改善约30%。两种不同初值情况下的优化效果相差很大是由于SA算法对初值依赖性很小，由此可看出，贪婪模拟退火算法有助于快速得到指派问题的最优解，在实际应用过程中可以在合理时间内，以较快的速度得到机位指派问题的满意解。
图1 贪婪模拟退火算法的收敛性 图2 典型模拟退火算法的收敛性
5 结语
针对枢纽机场运营管理中的停机位分配问题，本文提出了以旅客行走距离最短为优化目标的停机位指派的数学模型，并设计了求解该模型的贪婪模拟退火算法，整个过程分两个阶段进行，第一阶段求解，第二阶段优化，算例研究表明，该算法为利用计算机进行停机位自动分配并优化停机位结果提供了一种可行手段，并为停机位的实时指派提供了一种方法。
参考文献:
[1]Yu Cheng, 1997. A knowledge-based airport gate assignment system integrated with mathematical
programming [J]. Computers and Industrial Engineering 32,837-852.
[2]Yu Cheng, 1998. Solving push-out conflicts in apron taxiways of airports by a network-based
simulation [J]. Computers and Industrial Engineering 34,351-369.
[3]Shangyao Yan, Chia-Ming Chang, 1998.A network model for gate assignment [J]. Journal of Advanced
Transportation 32,176-189.
[4]Ali Haghani, Min-Ching Chen, 1998.Optimizing gate assignment [J]. Transportation Research A
32,437-454.
[5]Ahmet Bolat, 2000. Procedures for providing robust gate assignments for arriving aircraft[J]. European
Journal of Operational Research 120(2000), 63-80.
[6]Shangyao Yan,Cheun-Ming Huo,2001.Optimization of multiple objective gate assignments[J].
Transportation Research A 35,413-432.
[7]常钢, 魏生民. 停机位分配问题优化技术[J]. 中国民航学院学报, 2006, 24(2): 25-29.
[8]文军,孙宏,徐杰,梁志杰.基于排序算法的机场停机位分配问题的研究.系统工程, 2004, vol.22, No.7,
102-105.
物流配送中几种路径优化算法
捕食搜索算法 动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成 的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有 发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有 猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间 没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻 找猎物。 模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatory search algorithm, PSA)。基本思想如下：捕食 搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较 优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从 而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索 之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(traveling salesm an problem )和超大规模集成电路设计问题(very large scale integrated layout)。 捕食搜索算法设计 (1)解的表达 采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一 6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负 贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾 客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。 (2)邻域定义 4 仿真结果与比较分析(Simulation results and comparison analysis) 设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。
物流配送路径优化论文
山西工商学院 毕业设计 题目浅析物流配送路径优化问题 学生姓名杨美玲 学号200822054247 专业物流管理 班级08物流二班 指导教师李桂娥 二零一一年十月二十八日
目录 摘要 (ⅰ) 一、引言（问题的提出） (1) 二、物流配送路径优化问题的数学模型……………………………X 三、物流配送路径优化问题的遗传算法……………………………X （一）遗传算法的基本要素………………………………………X （二）物流配送路径优化问题的遗传算法的构造……………………X 四、实验计算与结果分析…………………………………………X 五、结论…………………………………………………………X 参考文献…………………………………………………………X 致谢………………………………………………………………X
中英文摘要 摘要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的遗传算法，并进行了实验计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方便有效地求得问题的最优解或近似最优解。 关键词：物流配送；遗传算法；优化 Study on the Optimizing of Physical Distribution Routing Problem Based on Genetic Algorithm Abstract：On the basis of establishing the optimizing model on physical distribution routing problem, this paper presents a genetic algorithm for solving this problem, and make some experimental calculations. The experimental calculation results demonstrates that the optimal or nearly optimal solutions to the physical distribution routing problem can be easily obtained by using genetic algorithm. Keywords：physical distributio n；genetic algorith m；optimizing
家乐福超市物流配送路线优化
学年论文之 家乐福超市物流配送路线优化 专业物流工程 班级 姓名 学号 日期
在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。 通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题，并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配送路线还可以进行再优化，从而达到运输成本最小化的目标。 关键词：物流配送；路径优化；节约里程算法
1.绪论 (1) 1.1选题目的和意义 (1) 1.2国内外物流配送路线优化研究现状 (2) 2. 家乐福超市配送路线现状 (3) 2.1家乐福超市概况 (3) 2.2家乐福超市配送路线作业现状 (4) 2.2.1 配送距离分析 (4) 2.2.2 车辆数分析 (5) 2.2.3 需求量分析 (6) 2.2.4 商品品种分析 (6) 2.3家乐福超市配送现有路线问题分析 (7) 3.配送路线优化建模与求解 (9) 3.1研究对象目标设定 (9) 3.2模型的构建 (11) 3.3节约算法 (12) 3.3.1节约算法的基本原理 (12) 3.3.2节约里程算法主要步骤 (13) 3.3.3基于节约算法的配送路线优化 (13) 3.3.4优化后的配送线 (24) 4.优化结果分析 (25) 4.1优化前结果 (25) 4.2优化后结果 (25) 4.3结论 (26) 5.总结与建议 (27) 参考文献: (28)
业务流程与组织结构优化
业务流程与组织结构优化 一、业务流程优化介绍 （一）定义 流程优化是一项通过不断发展、完善、优化业务流程，从而保持企业竞争优势的策略。在流程的设计和实施过程中，要对流程进行不断的改进，以期取得最佳的效果。对现有工作流程的梳理、完善和改进的过程，即称为流程的优化。流程优化不仅仅指做正确的事，还包括如何正确地做这些事。为了解决企业面对新的环境、在传统以职能为中心的管理模式下产生的问题，必须对业务流程进行重整，从本质上反思业务流程，彻底重新设计业务流程，以便在当今衡量绩效的关键（如质量、成本、速度、服务）上取得突破性的改变。 （二）目的 1、提高组织运作效率，降低整体运营成本 2、打破部门间壁垒，增强横向协作 3、管理层能够有效的监督和控制企业的整体运作 4、确保公司策略得以有效地执行，从而支撑战略的实现 （三）目标 1、总体目标 ?提高集团管控能力。 2、详细目标 ?确定与流程运行相适应的岗位设置和绩效考核的KPI指标体系， ?明确新的流程体系所需的IT支持 ?在试点范围内使流程操作人员掌握项目成果所需的知识与技能 ?较高且稳定的投资回报率与合理的财务结构 ?高素质的管理队伍与高效率的内部管理与决策 （四）影响 1、增强业务流程的可靠性 2、降低成本 3、提高顾客满意度 4、提高员工士气 5、减少官僚作风
6、提高报告的质量 7、更好的财务控制 （五）方法 系统化改造法以现有流程为基础，通过对现有流程的消除浪费、简化、整合以及自动化（ESIA）等活动来完成重新设计的工作。一般来说，外部经营环境相对稳定时，企业趋向于采取系统化改造法，以短期改进为主。从多数单位的具体情况来说，比较适宜的方式是采取系统化改造法，而且最好用流程图形式表现出来。 全新设计法是从流程所要取得的结果出发，从零开始设计新流程。 这两种流程优化方式的选择取决于企业的具体情况和外部环境。在外部经营环境处于剧烈波动状况时，企业趋向于采取全新设计法，着眼于长远发展而进行比较大幅度的改进工作。在企业客户服务流程中，多数问题出在客户的诉求需要经过多个环节才能得到响应。然而对于网络化的企业来说，其管理理念之一是对客户需求的“快速响应”，这种多环节的运作模式显然不适应。于是，基于信息化平台的新的客户服务流程就应运而生 二、业务流程与组织结构优化过程 1、业务流程总览 2、业务流程步骤
物流配送最优路径规划
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题
关于机场停机位分配方案模型的研究(20111129)
关于机场停机位分配方案模型的研究 中南财经政法大学信息管理与信息系统2009级0903班易盈盈0909030336 摘要：随着信息化社会的高速发展，人们的生活越来越依托于网络技术，本文主要讨论机场停机位分配问题即考虑如何在满足一定约束条件下，借助于网络信息系统为到达和离开机场的航班分配合适的停机位，保证航班正常且高效运行。本文关于机场停机位分配方案构建了3种模型，一是飞机最适应模型；二是乘客最短路径模型；三是二者均衡考虑，构建模型。该模型实施将为我国大部分机场运营管理中的手工机位分配所导致的效率低下问题带来可能的解决方案。实现计算机化机位分配，适应信息化的飞速发展，从而提高机场运营企业资源利用效率，降低运营成本，同时节省人力资源，因此具有重要的研究价值和应用价值。 关键词：机场；停机位分配；模型构建 a study on the airport gate allocation model Abstract: With the rapid development of information society, people's lives are increasingly relying on Internet technology, this article focuses on airport gate allocation problem is to consider how to satisfy certain constraints, by means of network information systems for the airport's flight arrival and departure appropriate allocation of parking bays to ensure the normal and efficient flight operation. This article about the airport gate allocation plan to build three different models, one is the best fit model aircraft; two passengers shortest path model; Third, a balanced consideration of both to build the model. The model will be implemented in most of our airport operations management manual seat allocation inefficiencies caused by bringing a possible solution. Computerized machine allocation, to adapt to the rapid development of information technology to improve airport operations business resource efficiency, reduce operating costs, while saving manpower resources, it has important research value and application value. Key words: airport; gate allocation; model building 1引言 1.1 背景 随着社会经济的快速发展，人们对于乘坐航班出行的需求日益增加，在促进民航规模迅速发展的同时，也使得机场停机位不足与航班数量不断增长的矛盾日益凸显。 1.2 现状 目前我国民航数量不断增长，人们出行对于飞机等交通工具的依赖也越来越大，这势必会导致空间资源的紧张，虽然可以通过扩大机场，增加设施缓解停机位分配不足的矛盾，但是从长远来看这一方案并不可行。因为一方面扩建机场需要大量的人力物力，对机场周围环境产生影响；另一方面这一方案有时间上的滞后性，由于机场扩建需要一定的工期，这会对现存的营业产生影响。传统的机位分配方案是
物流配送管理中路径优化问题分析
摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。 三、算法分析 对于本文的上述问题，有两种算法一(传统算法)和二(逆向标号算法)可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法[2]，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已
第三方物流运输方式和配送路径优化研究
第三方物流运输方式和配送路径优化研究 摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。
机场停机位分配问题研究
龙源期刊网 https://www.wendangku.net/doc/7a1372735.html, 机场停机位分配问题研究 作者：鲁文俊 来源：《中国科技博览》2016年第28期 [摘 ;要]随着国民经济的迅速发展，我国对民航的需求量也不断增长，各航空公司的飞机 数量也随之扩大，这为机场业带来广阔的发展空间，同时对机场的运行保障能力面临着考验。机场地面实际运行中停机位资源是运行的基础，停机位怎样分配关系着航班的保障车辆设备及相应保障人员的调度，停机位的分配方案也对机场和各航空公司的运行效率有着直接影响，因此对停机位如何分配的问题进行优化研究有着重要的实际应用价值。本文根据机场的实际运行等相关因素，基于动态分配的原则，对于有利于机场廊桥地利用率提升，从而对机场航班的运行效率有着积极地作用。 [关键词]机位资源 ;运行效率 ;动态分配 中图分类号：TU857 文献标识码：A 文章编号：1009-914X（2016）28-0152-02 引言 机场停机位的分配就是在多制约性因素（机型大小、机位大小、航班性质、航线性质）的条件下，在一定的时段区间内，为进港航班完成相应的预分配工作。机场停机位的分配通常有对机位预分配、机位实时分配两种形式;机位预分配是指在航班生产运行系统信息明确的条件下，对一定时段范围内的进港航班进行预分配;机位实时分配是指在机位预分配的基础上，由于航班延误、机械故障、空管流控等因素导致预分配的机位不能正常执行，从而要对进港进行相应的机位调配，保障进港航班的机位正常，减少航班的延误。 机场地面实际运行中停机位资源是运行的基础，机位的分配结果影响着其航班的旅客及其保障人员，停机位的分配对机场经济效益及其旅客满意度都有直接影响。机位资源的分配是机场运行指挥中心的核心业务之一，其分配中要考虑航空公司的指廊分配原则、航班的性质、机型、机位限制、过站的时间、航班密度等多方面因素。合理的机位分配不仅能减少航班延误，也能减少旅客从机位到进站口的步行时间和距离，提高旅客满意度。目前，民航的高速发展，机场的基础设施明显不足，限制了机场运营规模的提升，停机位的优化分配是一个重要的研究问题。 1 机位分配的问题描述 机位分配问题属于经典的分配问题，其中被安排者是机位，任务是待安排机位的航班。机位分配的特殊之处：有一些被分配者没有完成某些任务，任务比被分配者多，任务和被分配者是跟随时间变化的。机位分配中分配的航班是有明确时间规定的，而经典分配问题是没有任务完成的确定时间段的，因而机位分配相比较而言，更为复杂。
物流系统优化——定位——运输路线安排问题LRP研究评述
——第6届全国青年管理科学与系统科学学术会议论文集 2001年·大连 437 物流系统优化中的定位—运输路线安排问题 （ＬＲＰ）研究评述* 林岩 胡祥培** （大连理工大学系统工程研究所, 116023） 摘要 本文概述了物流优化问题中的定位—运输路线安排问题 （Location-Routing Problems, LRP ）的发展历程，并对LRP 的分类和解决方 法加以评述，最后就这一问题的发展方向进行简单地探讨。 关键词 LRP 物流 系统优化 运筹学 1 引言 新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，但是，由于它是一套全新的技术，同时还是一种全新的管理理念，所以其发展过程中必然存在一些难题。在电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在许多网站上成为现实；然而，我国传统的物流体系是在计划经济环境下建立、发展起来的，与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之 一。所以对物流系统优化的研究将会具有很大的现实意义。 国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了许多解决问题的算法。依据实际问题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线安排问题（VRP ）、定位—配给问题（LA ）、定位—运输路线安排问题（LRP ）等等，其中LRP 更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。 本文先从VRP 和LA 的集成来探讨LRP 的由来，然后讨论LRP 的分类，同时探讨LRP 的研究现状，并对LRP 的解决方法进行概述，最后就LRP 的未来发展方向作简要的讨论。 2 从VRP 、LA 到LRP ——物流系统的集成 依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线 * 国家自然科学基金重点项目(70031020) ** 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。
业务流程优化思维与方案
业务流程优化思维 与方案 1
业务流程优化思路和方法 信息化建设对于中国企业来说已不再陌生,但前期效果实在差强人意。以致企业信息化建设被称为”IT黑洞”。造成这种结果的原因很多,如管理软件系统不成熟,系统实施队伍经验不足等,但核心的问题是信息化建设并没有与适合企业的管理体系相结合。 企业信息化建设是以信息技术应用为基础的管理改造过程。业务流程优化过程不是单纯的管理技术问题,必须考虑现有和未来的信息技术应用,即应利用信息技术的手段固化管理体系,并提高信息交互速度和质量。 业务流程优化的过程 首先是现状调研。业务流程优化小组的主要工作是,深入了解企业的盈利模式和管理体系、企业战略目标、国内外先进企业的成功经验、企业现存问题以及信息技术应用现状。两者间的差距就是业务流程优化的对象,这也就是企业现实的管理再造需求。以上内容形成调研报告。 其次是管理诊断。业务流程优化小组与企业各级员工对调研报告内容协商并修正,针对管理再造需求深入分析和研究,并提出对各问题的解决方案。以上内容形成诊断报告。
基于信息化平台的客户服务流程 最后是业务流程优化。业务流程优化小组与企业对诊断报告内容协商并修正,并将各解决方案细化。 具体的业务流程优化的思路是:总结企业的功能体系;对每个功能进行描述,即形成业务流程现状图;指出各业务流程现状中存在的问题或结合信息技术应用能够改变的内容;结合各个问题的解决方案即信息技术应用,提出业务流程优化思路;将业务流程优化思路具体化,形成优化后的业务流程图。 业务流程优化的方法 当前,业务流程优化有两种方法,即系统化改造法和全新设计法。 其中,系统化改造法以现有流程为基础,经过对现有流程的消除浪费、简化、整合以及自动化(ESIA)等活动来完成重新设计的工作。全新设计法是从流程所要取得的结果出发,从零开始设计新流程。这两种流程优化方式的选择取决于企业的具体情况和外部环境。一般来说,外部经营环境相对稳定时,企业趋向于采取系统化改造法,以短期改进为主;而在外部经营环境处于剧烈波动状况时,企 3
智能算法在机场停机位分配
智能算法在机场停机位分配及优化问题中的应用 姓名：周蔷 学号: B0907119 E-mail:zhouqiang2000@https://www.wendangku.net/doc/7a1372735.html, 2009年6月11日研究背景 （一）机场实际运营的需要 在日益繁忙的干线机场和中枢机场，原来的简单调度方式已经不适应民航整体事业发展的需要，比如根据2002年某国内机场调查结果表明，由机场调度引起的航班延误占所有航班延误的15.45% 1.资源调度的优化可以提高运营效益 2.现代化的管理需要先进的技术手段 3.停机位分配问题是站坪控制的核心 4.提高机场的安全保障能力和服务质量 研究背景 （二）传统优化理论升级的需要 ?传统实际问题的特点 连续性问题?a?a主要以微积分为基础，且问题规模较小 ?传统的优化方法 追求准确?a?a精确解 理论的完美?a?a结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划、排队论、库存论、对策论、决策论等。 ?传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等） 研究背景 （二）传统优化理论升级的需要 ?现代问题的特点 离散性问题——主要以组合优化（针对离散问题）理论为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决策支持系统 大规模问题——并行计算、大型分解理论、近似理论 ?现代优化方法 追求满意——近似解 实用性强——解决实际问题 ?现代优化算法的评价方法 算法复杂性 研究背景 （二）传统优化理论升级的需要 现代优化( 启发式) 方法: ?禁忌搜索（Tabu Search,TS） ?模拟退火（Simulated Anealing,SA） ?遗传算法（Genetic Algorithms,GA） ?蚁群算法（Ant Colony Algorithms,ACA）
基于遗传算法的配送路径优化研究开题报告
北京师范大学珠海分校 本科生毕业论文（设计）开题报告
理论和实践的意义及可行性论述 (包括文献综述) 理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产 率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个 原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送 路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。 可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂 性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问 题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准 遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优 解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。 文献综述： [1]朱剑英?非经典数学方法[M].武昌：华中科技大学出版社，2001 [2]李敏强，寇纪淞，林丹，李书全?遗传算法的基本理论与应用[M].北京：科 学技术出版社，2002 [3]孙丽丽?物流配送中车辆路径算法分析与研究[D].上海：上海海事大学，2007 [4]盖杉.基于遗传算法的物流配送调度系统 [D].长春：长春理工大学，2007 [5]高运良，基于免疫遗传算法的物流配送V RP 求解[D].武汉：武汉科技大学， 2007 论文撰写过程中拟采取的方法和手段 本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德 算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整 个算法的时间复杂度和空间复杂度。
优化流程管理制度
流程优化管理制度 1.0目的 在成本、质量、服务和速度等方面取得显着的改善，使得企业能最大限度地适应以顾客、竞争、变化为特征的现代企业经营环境。通过辨识、分解、评估业务流程中各个环节，对不必要的流程进行删除、压缩、重排等流程管理手段，以有利于开发客户价值为标准，重新设计业务流程，重新建设组织架构，重新改造经营管理模式。从而保持企业在竞争中获得领先的竞争能力。 2.0适用范围 裕富宝厨具设备（深圳）有限公司所有设计的流程。 3.0程序 3.1董事长、董事或职能部门根据流程运行现状提出流程改进的目标或要求。 3.2流程总设计师根据3.1要求分析流程现状，确定流程优化层级（选取流程层级），确定是否对现状流程优化，还是对关键流程或流程体系优化。形成流程改进初步方案（确定流程优化路径）。 3.3根据流程改进的初步方案对现有业务流程评估。主要是通过评估、分析、发现现有业务流程存在的问题和不足，实现途径包括绩效评价、事故检讨、客户反馈、检查控制和学习研究等。 3.3.1绩效评价：根据公司、部门的目标绩效完成情况，分析评估相关业务流程的质量和运作状况。
3.3.2事故检讨：公司运营过程中发生较严重的事故时，应分析评估相关业务流程的质量和运作状况。 3.3.3客户反馈：流程客户（包括直接、间接客户和内部、外部客户）通过投诉、抱怨、调查反馈、消极反应等方式传递意见时，应分析评估相关业务流程的质量和运作状况。 3.3.4检查控制：主动性地对相关业务流程的运作状况进行定期或不定期的检查以及管理部门在行使审核程序时，都可以分析评估业务流程的质量和运作状况。 3.3.5学习研究：组织和个人在主动的学习过程中，以及在做标杆研究时，都可以对业务流程的质量和运作状况进行分析评估。 3.4流程分析。主要是分析流程评估中发现的问题和改善机会，为后一步的改进行动提供指引，分析内容包括性质分析、原因分析、干系分析和实施分析。 3.4.1性质分析：对流程评估中发现问题影响面和严重性进行分析，判断其类别和性质。 3.4.2原因分析：分析探寻问题产生的原因机理和影响因素 3.4.3干系分析：分析存在问题及潜在的解决方案影响、涉及到哪些关联方，对这些关联方影响的程度及其可能的配合程度如何等。 3.4.4实施分析：分析对发现问题进行优化改进的必要性、可能性、时间性和是否涉及关联流程的同步优化，即回答是否有必要改进、是否能改进、是否现在改进、是否需要和关联流程同时改进几个问题。
基于 GSAA 的停机位指派优化问题的研究
基于GSAA的停机位指派优化问题的研究 鞠姝妹1，许俐 （南京航空航天大学民航学院， 南京 210016） 摘 要：停机位的合理指派是机场地面作业中的一项核心任务，对减少枢纽机场航班中转时间起着重要作用，但是停机位指派问题是NP难问题，模型和算法都比较复杂。本文建立了以旅客满意度为优化目标的数学模型，并设计了一种贪婪模拟退火算法（GSAA），以求解枢纽机场的停机位指派问题。该算法首先根据贪婪算法FCFS 准则使“丢失”的航班数最少得到模拟退火算法的初始解，然后运用经典模拟退火算法求解出最优指派结果。数值仿真证明了模型和算法的有效性。 关键词：枢纽机场；停机位指派；旅客满意度；贪婪模拟退火算法 Airport Gate Assignment Problem based on GSAA JU Shumei, XU Li (School of Civil Aviation，Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China) Abstract: Airport gate assignment is a key task among the airport ground work which is important to reduce transfer time in hub airports. However, the gate assignment problem (GAP) is an NP-hard problem, its models and algorithms are complex. This paper proposed a model and a new greedy simulated annealing algorithm (GSAA) to resolve the GAP. The initial solution of the proposed algorithm is obtained through FCFS criterion of greedy method to minimize the “dropping” flights, and then the optimal solution is got by the traditional simulated annealing algorithm. Simulation result shows the validity of the model and the algorithm. Key words: hub airport; gate assignment problem; the degree of passenger satisfaction; greedy simulated annealing algorithm 1 引言 停机位分配是指，在考虑机型大小、停机位大小、航班时刻等因素的情况下，在一定时限范围内，由机场生产指挥中心为到港和离港航班指定适宜的登机口，保证航班正常不延误，为旅客上下航班提供登机门[1]。针对停机位分配问题，目前国外学者已经提出了多种分析方法，如专家系统、分支定界算法以及结合单纯型法和分支定界算法的优点提出的解决策略。此外还有一些基于数学模型的方法，它们的客观作用通常是减少旅客的步行距离、减少未被利用的停机位数量、减少使用停机位的时间段等问题。国内针对这方面的研究都相对较晚。 本文建立了以旅客满意度为优化目标的数学模型并设计了一种贪婪模拟退火算法（GSAA）以求解枢纽机场的停机位指派问题。 2 枢纽机场停机位指派模型描述 2.1 假设条件 在建立模型之前，首先引进三个假设条件： （1）容量满足假设。机场的航班量和时间分布保持在机场容量许可范围内，即在任意时 基金项目：民航总局软科学基金项目（MHRD0622） 作者简介：鞠姝妹（1984－），女，江苏，南京航空航天大学硕士研究生，从事交通运输规划与管理研究。
物流配送的车辆路径优化
物流配送的车辆路径优化 专业：[物流管理] 班级：[物流管理2班] 学生姓名：[江东杰] 指导教师：[黄颖] 完成时间：2016年6月30日
背景描述 物流作为“第三利润源泉”对经济活动的影响日益明显，越累越受到人们的重视，成为当前最重要的竞争领域。近年来，现代物流业呈稳步增长态势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业的市场需求持续扩大。特别是进入21世纪以来，在国家宏观调控政策的影响下，中国物流行业保持较快的增长速度，物流体系不断完善，正在实现传统物流业向现代物流业的转变。现代物流业的发展对促进产业结构调整、转变经济增长方式和增强国民经济竞争力等方面都具有重要意义。 配送作为物流系统的核心功能，直接与消费这相关联，配送功能完成质量的好坏及其达到的服务水平直接影响企业物流成本及客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，其中，车辆配送线路的合理优化对整个物流运输速度、成本、效益影响至关重要。 物流配送的车辆调度发展现状 VRP（车辆调度问题）是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序的通过，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量等限制）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为，不涉及时间的是路径问题，涉及时间的是调度问题。VRP示意图如下 当然，VRP并不止是这样的一个小范围，而是又更多的客户点与一个仓库链接，从而达
到一整个物流集群。 根据路径规划前调度员对相关信息是否已知，VRP可分为静态VRP和动态VRP，动态VRP 是相对于静态VRP而言的。静态VRP指的是：假设在优化调度指令执行之前，调度中心已经知道所有与优化调度相关的信息，这些信息与时间变化无关。一旦调度开始，便认为这些信息不再改变。 而VRP发展到现在的问题也是非常突出的，例如，只有一单货物，配送成本远高于一单的客户所给的运费，在这种情况下，该如何调度车辆？甚至还有回程运输的空载问题，在这些问题之中，或多或少都涉及到了VRP的身影，那么在这样的配送中怎么有效的解决车辆的路径优化问题就是降低运输和物流成本的关键所在。 解决怎么样的问题？ 现如今对于VRP研究现状主要有三种静态VRP的研究、动态VRP的研究以及随机VRP的研究。 而我对于VRP的看法主要有以下几点。 有效解决VRP或者优化车辆调度路径优化问题，那么将非常有效的降低物流环节对于成本的比重，有效的增大利润。 而我想到的方法，就是归类总结法。 建立完善的信息系统机制，将订单归类总结出来，可以按地区划分出来，一个地区一个地方的进行统一配送，这样也有效的降低了物流配送的车辆再使用问题，降低了成本。如下图所示。 仓库 客户 变换前 由上图可以看出来这样的路径，车辆需要来回两次，严重增加了配送成本，也增加了运输成本，使得利润并不能最大化。