航空客运票务免费接送服务系统的架构设计.doc

航空客运票务免费接送服务系统的架构设计基金项目：国家自然科学基金（70625001, 70721001）；教育部科技研究重点项目（104064）；教育部新世纪优秀人才支持计划（NCET-04-280）。作者简介：杨培颖（1982），女，博士生，Email:唐加福(1965), 男, 教授, 博士生导师, 主要从事生产与物流运作管理等方面的工作。杨培颖，唐加福（东北大学教育部流程工业综合自动化重点实验室，沈阳 110004）摘要：本文以实现航空客运票务免费接送顾客的集约化服务为背景，首先对车辆调度与分配的相关问题进行了简单的综述，对航空客运票务免费接送服务系统的运作流程及特征进行了定量化的分析。基于以上分析构建出航空客运票务服务免费接送系统的架构，并根据此架构，提出了可行性的设计。本文能够较好的解决目前航空客运票务公司普遍存在的人工调度接送服务与动态客流脱节而发生矛盾的问题。关键词：航空客运票务服务；多目标车辆调度；优化模型0 引言近年来我国航空服务行业发展迅速，业内之间的竞争也日益激烈。服务性企业的服务质量已经成为令消费者满意的重要因素，它的重要性等同于成本，或者从某种意义而言，它的重要性甚至超过了成本价值。航空票务公司就是一类典型的服务型企业，其主要业务功能是代售各个航空公司机票，并为有需要的旅客提供接送服务。随着社会、经济活动量的增加，人们的商务性、文化性、生活性往来不断增多，越来越多的旅客出行选择乘坐飞机的同时，对票务附加值服务的要求也越来越高。这使得航空客运票务公司在业务需求不断增加的同时，面临着巨大的挑战和商机。但是目前多数航空票务公司在票务附加值服务方面，还停留在低水平状态。航空票务服务仍相对薄弱，商旅物流中的许多问题，如客流组配方案、配送车辆的管理调度、运输的最佳路线选择等，还处于半人工化决策状态；对于在途配送车辆的管理，在途客流的跟踪几乎处于束手无策的状态；而与之相配套的物流设备都比较陈旧，与国外以机电一体化、无纸化为特征的配送自动化、现代化相比，差距很大。在制定车辆分配和调度计划时，还在采用人工经验制定的形式，这需要消耗大量的人力、物力，且工作效率很低。更主要的是，这种单纯以人的经验来制定的调度计划，已经逐渐不能适应现代社会大物流的动态要求。为了不断提高航空客运票务公司的服务水平，为了使国内航空客运票务公司服务与国际一流水平接轨，我们提出并设计了航空客运票务公司免费接送服务系统模型。通过这个系统模型，可以以经济性、准时性、灵活性的高质量软件设计来支持能够适应动态性客流变化的票务服务，进而进一步提升航空客运票务公司的竞争能力，并以集约化途径实现公司服务成本的降低。1 相关工作车辆路径调度问题是1959年由G.Dantzig和J.Ramser首先提出来的,当时他们利用整数规划模型处理了包含大约10到20个顾客点的小规模问题，这一阶段可以称之为车辆路径问题的发轫阶段，即理论奠基阶段。这一问题的提出很快引起运筹学、管理学、计算机应用、组合数学、图论等学科的专家学者的高度重视1-4。在上世纪八九十年代，许多外国学者对此问题进行了大量的理论研究和实验分析,取得了很大的研究进展。在文献5中，Bertsimas总结提出了解决动态车辆调度问题的几种策略，在文献6中，提出了一种单车辆的动态车辆调度问题算法，在文献7中，作者在他的博士论文中详细阐述了动态车辆调度问题的各种特征、算法策略。Mingozzi8 提出了一个整数规划模型描述MDPVRP，该模型是对有能力限制的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)集划分模型9的扩展。这一阶段可称之为车辆路径调度问题的理论发展阶段。其研究结果现在已经广泛地影响了运输系统、物流配送系统、快递收发系统的发展。而我国对有关车辆路径问题的研究是在20世纪90年代以后逐渐起步的。进入二十一世纪后，我国学者对车辆路径调度问题理论研究逐渐增多，其中，马为民10在其博士论文中用在线和竞争策略研究了带时间窗的开放式VRPTW，冯萍11在其硕士论文中用插入法、遗传算法、模拟退火算法研究了带软时间窗的车辆路径问题VRPSTW。总体来说，目前我国对车辆调度问题的理论研究比较广泛。本文我们综合以往的研究成果提出了航空客运票务免费接送服务系统的框架，通过对此框架的完善以期能够支持目前国内一流的航空客运票务服务。2 航空客运票务免费接送服务优化模型与系统设计与分析2.1基本流程一般来说，当顾客在票务公司订购机票时，票务公司首先会询问顾客是否需要免费接送服务。然后记录下需要该项服务的顾客信息，比如：该顾客的航班号，出港时间，需要的接送地点等，然后将这些信息积量，逐步形成信息库。继之，利用这些信息库内的数据，演绎推倒出规律性的路径走向模式，基于对这些模式的宏观性统筹，决策者可以对每个顾客的接送时间，每个车次的出发时间，每个车次需要接送的顾客以及这些顾客的接送顺序做出优化性的安排。最后根据做出的优化性安排提前通知顾客接送的时间。其基本业务流程如图1所示：图1 航空客运票务公司免费接送服务的基本业务流程图2.2优化模型的组成分析现有的调度系统一般都是采用动态调度模型。在动态调度模型中，每辆车在每次动态调度过程中，都需要先后接送多名旅客，这样就使得较早被接送的旅客对航空客运票务公司的满意度下降，尤其对VIP客户而言，如果较早的被接送，会较多的浪费他们的时间，这就可能导致此类客户流失。所以，本文考虑以静态、动态相结合的方式来实现该系统模型。静态调度模型，对潜在旅客的乘车路线加以分析，设置出一条或者多条的固定线路。固定线路的车型选择、站点设置和发车时间间隔要充分考虑多方面因素。车型选择方面，综合考虑城市规模和潜在旅客人数，可设定为小巴和中巴。在线路站点选择方面，要兼顾城市的商务区、商业区、高档住宅区和交通热点区。在发车时间间隔方面，可以将站点之间的运行时间考虑成常值，也可以考虑成随时间的变化而变化。而且，在发车时间间隔方面，还要考虑到航班出入港情况。一天当中，早晨和中午的出港架次比较多，下午和傍晚的入港架次比较多，在这些进出港密集的时间段可以使发车的时间间隔缩短。静态调度模型可以集中解决大部分旅客的接送问题，但是还存在一些旅客，他们提供的接送服务的地点往往远离静态调度模型中的沿途经过的站点。这时，就需要动态调度模型来完成对他们的接送服务。远离静态调度模型线路的旅客相对人数较少，所以，在车型选择上我们可以采用单一车型，即小轿车来完成接送任务。对于VIP客户和有特殊要求的客户，我们同样将其纳入动态模型服务系统，来实现对他们的服务。运送方式可以以专车单一服务为主。本系统正是通过这样的静态、动态相结合的模型来实现免费接送服务成本最小化和顾客满意度最大化的多目标模型。2.3本系统模型建立的表述本文将航空客运票务免费接送过程考虑成一个静态动态结合模型。旅客关心的主要问题是能否被按时接送和能否及时抵达目的地，以顾客等待车辆的时间作为衡量顾客满意度大小的标准。航空客运票务公司关心的是成本问题，其中包括车辆的运输成本以及车辆的固定发车成本。本模型的评价标准综合考虑影响旅客满意度和公司成本的各种因素，将这些因素纳入多目标模型的数学处理之中。如果本系统用户主要关心的是降低成本问题，那么可以以最小化成本为目标，将顾客满意度作为约束条件建立单目标数学规划模型。就本系统功能而言，以上单目标的数学规划模型是被包容在本系统之中的。本文将该问题描述成以最大化顾客满意度，最小化运输成本的多目标模型。首先作如下假设：(1) 一个车辆从发车地出发接送顾客往返一次机场为一个车次，同时假设车辆的出发地不变，即只有一个出发地；(2)双车型问题，在静态模型和动态模型中使用不同的车型； (3）静态模型中的路线为一条，且固定了若干乘降点；(4)旅客出发点到静态模型乘降点的时间，计入旅客满意度计算；(5)车辆到达乘降点后无等待时间，且不计算服务时间；(6)车辆匀速行驶，行驶时间与行驶距离成正比；(7)旅客出现在静态模型中每站的人数成均匀分布；(8)在静态模型中，站与站之间的运行成本相同；(9)在静态模型中服务成本和旅客坐车距离成正比。在一个计划周期内，用表示工作计划的时间范围；表示静态模型下乘降点的旅客人数；表示动态模型下乘降点旅客人数；表示动态乘降点的顾客必须到达机场的期限时刻，由航班时间和一定的松弛时间来确定；表示动态模型中乘降点软时间窗12的下限和上限；分别表示动态模型中乘降点硬时间窗13的下限和上限；表示动态模型中车辆从乘降点直接运行到乘降点的最短运输时间；表示静态模型中车辆的最大运载能力；表示动态模型中车辆的最大运载能力；表示航空客运票务公司在静态固定路线中可用的最大车次数量；表示航空客运票务公司在动态路线中可用的最大车次数量；表示静态固定线路的站点和顾客出发点之间的距离；表示静态模型中固定线路站点可接收服务的半径范围；表示需要服务的总人数；表示静态固定乘降点服务的总人数；表示静态模型中旅客乘坐一站的费用；表示旅客需要在静态模型路线中乘坐的站数； 是旅客能忍受的最长等待时间；表示车次从出发地出发的时刻；表示车次到达机场的时刻；在动态模型中，用表示车次是否被使用的0-1变量；表示乘降点是否由车次接送的0-1变量；在动态模型中，表示乘降点和是否由车次直接接送的0-1变量，即车次在接送乘降点和的旅客时中间不经过其它乘降点，则=1，反之，=0；表示车辆到达乘降点的时刻； 在以上的假设下，数学模型描述为如下： (1) (2) min (3) (4) (5) (6) (7) (8) , (9) (10) (11) ， (12) ， (13)如果则 (14) (15) ， (16) (17) (18) (19) (20)(1)式表示最小成本；(2)式表示最大满意度，且其中表示在动态模型中第个顾客点的满意度函数，表示为式(21)；(3)式保证最短运行时间； (4)式表示名旅客通过固定路线时的总成本；(5)式表示是关于的一个函数，是常量；(6)式表示静态模型里总的客户满意度，其中表示车次运行时间间隔分布；其中当顾客等待时间超过旅客能忍受的最长等待时间后，满意度为0；(7)式车载能力约束式；(8)式保证所有计划时间安排在工作计划的时间范围内； (9) 式保证每个顾客点的顾客都能按时到达机场；(10)式保证硬时间窗约束；(11)式为车载能力约束；(12)-(13)式保证接送每个顾客点的时间是在车辆的出发和到达时间之间；(14)式表示如果顾客点和被同一辆车直接接送，保证接送时间差的准确；(15)式表示每个顾客点的顾客只由一辆车接送，(16)式表示车辆路径问题中出度与入度的约束；(17)-(18)式表示0-1变量之间的逻辑关系；(19)式保证所有计划时间安排在工作计划的时间范围内。 (21)2.4本系统目标设计本论文建立的车辆分配与调度决策支持系统，旨在帮助票务公司智能化地完成免费接送服务中车辆的分配与调度，能快速合理地制定相应的计划，从而使系统对实际问题的变化能够做出快速反应，提高系统的动态适应能力，为公司的后续服务工作奠定智能化数据化基础。系统具体目标如下：（1）完成接送服务中的车辆分配与调度工作：制定合理的运输计划是本系统要完成的主要目标，其制定计划的合理性、及时性直接影响公司后续服务工作的效率。由于制定计划涉及的信息量大，且种类繁多，因此，在本系统中，要充分考虑到客户的各种要求，做到全面及时地对运输计划进行制定，使系统更加严密。（2）系统模型库和方法库的维护和补充：周密的运输计划要得以顺利进行，需要有强大的模型库和方法库支持，它的构建和维护直接影响着系统的效率。模型库和方法库可以因时因地因情况不断地扩充，为用户提供更多的选择方案，使系统更加完善，功能更加强大。（3）提供给用户多目标选择的系统：系统可以根据用户需要选择以最大顾客满意度或最低运行成本为单目标进行调度分析，也可以以两者综合的多目标进行调度分析。2.5 系统结构设计根据上节中对车辆分配与调度决策支持系统的需求分析。车辆分配与调度决策支持系统的层次结构如图2所示。系统主要包括三个层次：基础数据管理层、业务管理层和技术支持层。基础数据管理层的具体功能子模块为：客户基本信息管理、车辆基本信息管理、接送网络管理、人员组织结构管理；业务管理层的具体功能子模块为：客户管理系统、接送车辆管理、运输计划编制管理、运输计划变更管理。接送车辆管理运输计划编制管理运输计划变更管理客户管理系统业 务 管 理 层客户基本信息管理车辆基本信息管理人员组织结构管理接送网络管理基 础 数 据 管 理 层技 术 支 持 层图2 车辆分配与调度决策支持系统的层次结构根据上图，可以将系统分为信息管理子模块、查询分析子模块、运输计划安排子模块和系统维护这四个子模块。(1)基本信息管理模块这部分主要是管理系统中所需要的基本信息，包括客户信息、车辆信息和会员类型信息。能实现客户和车辆信息的新建、修改和删除，为系统制定运输计划时提供了基本的数据来源。客户信息包括客户编号、客户姓名、年龄、性别、身份证号码、需要接送的地点、时间、会员信息和其它需要说明的信息。车辆信息包括车牌号、司机姓名、电话和其他需要说明的信息。客户信息和车辆信息为系统制定车辆分配与调度计划提供基本的数据信息。会员类型信息用于设置客户的级别。可以根据客户的订机票数或其他信息设置客户的级别，然后根据客户的级别设置相应的权限，享有相应的优惠权利。基本信息是制定运输计划的数据基础，在需要时，操作员可以对基本信息进行添加、修改、删除等基本信息的操作。(2)运输计划制定模块运输计划制定模块是整个系统的核心部分，它是根据客户所输入的需要接送的信息以及接送车辆的信息，制定相应的接送计划。制定计划时，以日为单位制定计划，操作员应在运输计划实施的前一天或两天制定合理的计划安排。在制定计划时，可以选择不同模型和算法，以适应不同情况下需要制定的不同的运输计划。不同的模型和算法的目标与约束不一样，需要设定不同的参数，在本文中主要以最大客户满意度和最小成本的多目标模型为主。(3)分析查询模块分析查询模块对系统中的信息进行综合的查询，从而使用户能够全面地了解车辆分配与调度的状况。它主要可以用来查询两方面的信息。一是客户和车辆的信息，二是制定的运输计划。应用该功能模块时，用户能查询到客户和车辆的全部信息，包括它们的基本信息和是否被制定计划的信息。在查询制定的运输计划时，系统则可以实现运输计划的灵活查询和动态统计等功能。(4)系统管理模块系统管理是非常简单但又非常重要的一个环节，为车辆与调度决策支持系统提供系统基础管理。包括系统进入、维护、用户登录、用户退出、密码管理等功能，为系统的安全性提供保障。在系统运行时，会出现用户登录的界面，需要操作员输入自己的用户名和密码。只有当用户名和密码正确时，才能登录到车辆分配与调度决策支持系统。这个模块还可以进行增加操作员、修改密码等功能，以更好地维护系统的安全运行。3结论和展望 本文以航空客运票务公司免费接送顾客为背景，综合考虑影响公司票务额和公司的成本的各种因素，以提高客户满意度和降低公司成本为目标，分析了其业务流程，考虑了在业务流程过程中会遇到的问题。在此基础上，本文构建了航空客运票务免费接送系统的框架，依据本框架，本文给出了相应的数学模型，并进行了简要的分析。此框架的意义在于对免费接送服务的业务流程进行合理的安排及优化，辅助决策者做出更加合理的调度，以达到提高服务质量和降低运营成本的目的。以下问题将在进一步研究过程中逐步解决：旅客流呈长时间的不定时状态和不定量状态，且在节假日客流突发，呈井喷势，致使航空客运票务公司不能从容应对应变；目前本系统还不能支持对应突发地质性灾害、突发气象灾害的紧急预案的建立。参考文献1 Dror M, Trudeau P. Stochastic vehicle routing with modified savings algorithm J. European Journal of Operational Research, 1986, 23(2):228-235.2 Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries J. Discrete Applied Mathematics, 1994, 50(3): 239-254.3 Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem J.Computers & Operations Research, 1996, 23(3): 229-235.4 Russell R A. Hybrid heuristics for the vehicle routing problem with time windows J. Transportation Science, 1995, 29(2): 156166.5 Bertsimas,Van Ryzin. A stochastic and dynamic vehicle routing problem in the Euclidean plane J.Operations Research.1991,39(4)6 Bertsimas et al.Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehiclesJ.Operations Research.1993,41(1)7 Allan Larsen.The Dynamic Vehicle Routing ProblemD,IMM.DTU Book binder Hans Meyer,20018 Mingozzi A. The multi-depot periodic vehicle routing problem J. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2005, 3607: 347-350.9 Fukasawa R, Lysgaard J, de Aragao M P, et al. Robust branch-and-cut-and-price for the capacitated vehicle routing problem C. Integer Programming and Combinatorial Optimization 10th International IPCO Conference. Lecture Notes in Computer Science, 3064, Springer-Verlag, Berlin, 2004.1-15.10 马卫民，第三方物流配送优化问题及其竞争策略D.西安：西安交通大学博士学位论文，2003.11 冯萍，退火遗传算法在运输路线规划中的应用D.西安：西安交通大学硕士学位论文，2001.12 K. Fagerholt. Ship scheduling with soft time windows: An optimization based approachJ. European Journal of Operational Research. 131, pp.559-571.13 X. Wang and A. C. Regan. Local truckload pickup and delivery with hard time win