《高速公路联网收费ITS中车辆调度问题研讨》由会员分享，可在线阅读，更多相关《高速公路联网收费ITS中车辆调度问题研讨（10页珍藏版）》请在金锄头文库上搜索。
1、n 目前文档修改密码：8362839ITS中车辆调度问题研究河南省高速公路联网收费工作领导小组办公室 (E-mail: )摘要：在智能交通系统（ITS，Intelligent Transportation Systems）的各个子系统中，车辆调度应用非常广泛，但目前大都是针对物流公司车辆动态调度问题，很少应用ITS问题上。本文一方面根据实际状况，提出ITS中车辆调度问题，并分析了运送网络的特点，建立了模型。本文综合运用多种运筹技术，提出一种动态规划措施，为车辆调度问题提供了较好的解决方案。最后分析了现实中运送网络状态变化的类型与形式，并针对不同的状况，提出有效的对策。核心词：智能交通系统(IT
2、S)；车辆调度；运送网络；原子规划0 引 言智能交通系统（ITS，Intelligent Transports Systems）就是将先进的信息技术、传感器技术、数据通讯技术、自动控制技术、运筹学、图像分析技术、计算机网络和人工智能等有效地综合运用于整个交通管理体系,在系统工程综合集成思想指引下,建立起实时、精确、高效的交通运送综合体系。在ITS的各个子系统中，车辆调度问题（VSP，Vehicle Scheduling Problem）具有重要地位和作用，例如公交车辆调度、交通信息发布、智能途径调度等。车辆调度问题(Vehicle Scheduling Problem)一方面由Dantzig和
3、Ramser于1959年提出，它重要探讨：组织的行车路线，能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下，有序地通过一系列供应点或需求点，达到诸如路程最短、费用最小，耗费时间尽量少等目的1 7。本文综合应用多种运筹技术，提出一种迅速搜索措施，为集货和送货一体化、多供应点、多需求点、多运力点（车场）、单车型条件下的车辆调度问题提供了较好的解决方案，并且分析了现实中运送网络状态变化的类型与形式，并提出有效的对策2 8。1提出问题并分析建模1.1 提出问题设某运送网络有M个供应点（即S点，下同），N个需求点（即R点，下同），L个运力点（即C点，下同），每个运
4、力点只能接受自己发出去的车。每个S点可供应量为si（i=1，2，M），每个R点的需求量为rj（j=1，2，N），每个C点可发出车辆数为ck（k=1，2，L），车型均相似，载重量都为Q，求满足货运需求的路程最短的车辆行驶路线；运送网络中随时也许浮现新的S点或R点，求此时的行车路线规划；由于R点的需求量是由经验估计拟定的，也许会发生估计需求量不小于实际需求量的状况，需要将已经运往该R点的货品运回到其他S点或R点3 4。1.2 物流网络结点分析运送网络结点有三类：供应点、需求点和运力点。多种结点有如下状态： 供应点有三种状态：一般状态、无存货状态、有需求状态（只有当浮既有优先供应权的需求点时，供应点
5、对该需求点体现出这种状态）。 需求点也有三种状态：一般状态、已满足状态、有优先供应权状态（由于对需求点需求量的估计错误，导致向该需求点的运送数量超过实际需求量，由于需求点货品的存储条件差等因素，需尽快将多余货品运回，此时，运送网络中的供应点和其他处在一般状态的需求点，对于该需求点来说都是需求点）。 运力点有两种状态：有运送能力状态、无运送能力状态。1.3 模型建立先对一般状况下的车辆调度问题建模，而暂不考虑运送网络的突发状况。设：1，第p个运力点的q号车从i点行驶到j点0，第p个运力点的q号车不从i点行驶到j点为从供应点i点到需求点j点的供货量，则可得车辆优化调度的数学模型如下： i=1，2，
6、M （1） j=1，2，N （2） （3） （4） j=1，2，N （5）0或1 i，j=1，2，M+N+L；p=1，2，L；q=1，2，cp （6） i=1，2，M；j=1，2，N （7）阐明：dij表达从i点到j点的距离。约束（1）表达供应点i的总供应量不不小于等于其可供应量；约束（2）表达需求点j从各供应点的供货量之和等于其总需求量；约束（3）表达任何一种网络结点向其他结点发出的车辆总数等于接受的车辆总数；约束（4）表达运力点的存有车辆数不小于等于其向供应点和需求点发出的车辆之和；约束（5）表达需求点接受的车辆数与载重的积不小于等于其需求量5 6 10。2 解决方案2.1 为需求点分派运
7、送车辆的原则分析从总行驶里程至少的角度来考虑，如果给某些需求点都选定了一种运力点，那么从该运力点只派一辆车给这些需求点最经济。但事实上很难准时完毕运送任务，也是对运送能力的挥霍。因此，这里我们将每个需求点都至少分派一辆车，并根据任务量的大小和时间的急切限度来分派车辆的数量。如果某需求点的需求量太少，且任务时间宽裕，也可不分派，等其他需求点的车辆完毕任务后，再完毕该需求点任务11。2.2 单车运送状况下的行车路线规划1) 为需求点选择运力点：1. 找出各未分派车辆的需求点的涉及一种一般状态的供应点和一种有运送能力的运力点的最短初等圈或环；2. 对所有初等圈或环进行比较，找出总行程最短的初等圈或环
8、，这样拟定了一种需求点的运力点。3. 设该运力点已经派出一辆汽车完毕向该需求点的第一次运送，将此时各结点的状态设为运送网络的最新状态，反复环节1，直到对所有的需求点都分派完毕为止。2) 整车运送部分。设各车辆都向需求点完毕第一次运送，那么此时的运送网络达到运送规划的原则状态，可以通过运送规划来拟定下一步的运送任务。如下两条原则可以协助寻找最佳的行车路线：1. 整数倍原则：如某个供应点向某个需求点的运送量超过是汽车载重量的一倍或者几倍，那么运送量除以汽车载重量的整数部分要优先运送。2. 距离优先原则：距离较近运送任务的优先运送。由于运送网络是动态的，随时也许浮现意外状况，我们应在最短的时间内完毕
9、更多的任务。由于这两条原则在某些时候是矛盾的，我们主张根据运送网络浮现意外状况的频率来安排这两条原则的先后顺序。如果意外状况浮现频率较高则合用距离优先原则；反之则合用整数倍原则。一般状况下，应当在整数倍原则下使用距离优先原则。3） 非整车运送部分。通过上一步，此时的运送网络状况是yij yj1，（i=1，2，n），则标为Sj点。设共找到n个S点。3） 任意排列n个S点，每一种排列作为一种方略。1 若在某Sj点（jn），有yjkQyp1（p=1，2，j），且yjk+yp1+yj1Qyq1（p=1，2，j1；jR1-S1-R1-R2-C，C2的行车路线：C-R2-S2-R2-S2-R2-S2-R2
10、-C，可以调节为：C1的行车路线：C-R1-S1-R1-R2-S2-R2-C，C2的行车路线：C-R2-S2-R2-S2-R2-C。下面以一种最简朴状况下的例子来阐明一次行车路线规划措施：设运送网络中有两个供应点（S1，S2），两个需求点（R1，R2），一种运力点（C），其中每个供应点向需求点的供应量都不不小于Q，数据如表2.1、2.2：表2.2 结点距离表S1S2R1R2CS10S2800R170500R23050800C40600表2.1 供应量表R1R2S115S221目前各需求点的运送车辆都只有一辆，分别为C1，C2，汽车载重量都为6，各辆车的已规划的行驶里程分别为：200，300，求此时的行车路线规划。解：最先完毕已规划任务的C1，则从R1开始规划，括号中的数为该点的状态，第一种数是车辆的总行驶里程，第二个数是目前该车的载重量：S1S2R2R1R1R2CCR2R2S1S1R2R2CC（480|0）（400|3）（350|4）（270|1）（960|0）（900|0）（8
