城市配送车辆

城市配送车辆（精选7篇）

城市配送车辆 篇1

摘要：本文主要从多配送中心联合配送的车辆动态调度模型、城市配送路线优化的智能算法以及实时监控的城市配送车辆调度动态管理方案的研究进行阐述, 以期为解决车辆的配送线路问题提供参考资料。

关键词：城市配送车辆,路径模型,算法,研究

社会商业化和经济全球化的时代的到来, 让服务商和物流商清楚地认识到物流配送车辆优化调度的重要意义, 既可以降低商品物流成本, 更能提高客户服务水平, 可谓一举两得, 也是对物流企业品牌树立和生存发展至关重要的。

一、多配送中心联合配送的车辆动态调度模型的研究

提高配送网络的运行可靠性和有效可达性, 是物流配送运输网络优化的主要目标, 因此, 以物流配送运输网络畅通可靠度最大为目标进行建模。笔者根据现在很多城市物流配送的多品种、小批量、多批次和短周期等特点, 主要考虑以下约束条件:各条配送路线的货物总量不得超过车辆容积及载重量的限制;在物流中心现有运力允许的范围内;在配送过程中, 每个配送点只能访问一次, 且必须访问一次;每辆车只能服务一条线路, 且每辆配送车从配送中心出发, 最后必须回到配送中心;配送费用应当控制在一定水平下。遵循上述约束条件, 建立优化模型如下:

式中:ψn为网络中第n条配送线路的畅通可靠度;q为第n条线路所安排车辆的载重;q为第n条线路上所有配送点货物总量;N为配送线路的总体数目;M为物流中心配送车辆数;

A为某种确定水平下的费用定额, 为常数, 可根据经验值确定。

二、城市配送路线优化的智能算法的研究

城市配送中的多配送中心, 多种类货物的车辆调度问题是NP-Hard问题的组合, 是多目标优化问题。根据物流配送网络系统的具体情况, 笔者选择蚁群算法进行系统优化的研究分析。

所谓蚁群算法, 就是人类在观察自然界真实蚂蚁觅食的过程中总结出来的仿生优化算法, 它在短短的十余年的发展历程中展现出顽强的生命力, 成功地应用于解决旅行商问题 (traveling salesman problem, tsp) , 车间作业调度问题 (job-shopscheduling problem, jsp) , 车辆路径问题等组合优化问题。

我们用蚂蚁替代车辆, 当下一个要服务的配送点会使运载总量超出汽车载重量, 就返回到配送中心, 表示这辆车完成此次运输。然后换一辆车接着出发服务其余配送点, 直到所有配送点都得到了一次服务, 此时代表蚂蚁完成一次巡游。当所有蚂蚁都巡游一次, 记为一次循环。一次循环后, 根据各蚂蚁巡游历程的好坏 (目标函数值) , 计算信息素增量, 更新相关路径上的信息素。具体实现步骤如下:

步骤1初始化各基本参数, 置nc=0;

步骤2计算转移概率;

步骤3根据计算出的转移概率和随机产生的q值, 为每一只蚂蚁选择下一条移动的路径;

步骤4当每一只蚂蚁都走过一条边到达下一配送点后, 就按局部更新规则对这条边进行一次信息素的局部更新;

步骤5对每一只蚂蚁重复以上循环执行步骤2到步骤4, 直到所有的配送点皆有蚂蚁走过且配送点的需求得到满足;

步骤6在生成的全部路径中找出符合模型最优目标的路径, 则走过该路径的蚂蚁就是最优蚂蚁;

步骤7对最优蚂蚁所经过的每一条边, 按全局更新规则对这条路径进行一次信息素的全局更新;

步骤8重复执行步骤2到步骤7, 直到执行次数nc达到指定的最大迭代次数或连续若干代内没有更好的解出现为止。

配送网络畅通可靠度的最优意味着配送的延误出现的概率最小, 也即为对配送的有效可达性的最有力的保障。

三、实时监控的城市配送车辆调度动态管理方案的研究

(一) 降低成本, 提高效率

车辆作业流程的产生源于对物品诸要素 (收件人规定的时间段、重量、体积、货品类型、递送方式、跟踪要求/贵重物品) , 环境诸要素 (收件人地点、车辆禁驶区域和路段、街区宽窄、库房地点) , 车辆诸要素 (容积、载重量、车况、车辆类型、历史路况) 等诸多因素的综合自动规划, 由优化算法产生作业方案 (即目标、资源的合理利用和搭配) , 安排最佳的配送、揽收方式 (人或车, 专递或转递) , 最佳的行车路径, 最佳的收递顺序。目标是以最低的成本、最短的时间、最高的效率处理完成最大的业务量。

(二) 分析数据, 为决策提供依据

原配送体系的低速度、高成本瓶颈被突破后将衍生出基于高速度、低成本的新业务。利用作业系统数据库信息, 结合图形分析技术为管理层提供有力的运作分析数据, 为企业有效的经营决策提供依据。

(三) 提高承载能力

物流速度加快后, 业务承载量将加大, 系统可以方便地实现回程配货, 中心提前在线预知车辆的实时信息及精确抵达时间, 根据具体情况合理安排回程配货。

(四) 提高服务质量, 树立良好的企业品牌形象

物流活动是向客户提供及时、准确的产品递送。可以说, 客户服务是发展物流战略的关键, 采用信息化技术, 提高客户需求的响应速度, 增加服务种类, 实时反馈货品信息 (货品跟踪。对客户来说最需要了解的是物品的流通过程中物品是否安全、准确地到达指定的地点) 。物流企业应该利用现代信息科技, 提高服务质量, 树立良好的企业品牌形象。

城市配送车辆 篇2

目前，具有小批量、多批次特点的实时的城市配送的不断发展大大增加了配送成本，不合理的配送方案会严重增加城市交通负担。与城际配送等长距离的配送相比，城市配送货物需求点繁多且分布不均匀、单批需求量小且时常发生变动、道路堵塞情况时有发生，初始规划路线往往不能保证最小化企业运输成本，而且顾客可以通过移动电子商务平台随时随地进行订单的添加、取消和订货量的变更，加大了对配送实时响应性和灵活性的要求，增加了配送路径安排的难度。

实时的城市配送需要借助地理信息系统（GIS）、全球定位系统（GPS）、智能交通系统（ITS）、移动电子商务平台（MC）和全球移动通讯系统（GSM）等技术工具实时地获取动态信息，而调度中心要不断的合并新信息，在每个动态事件发生时刻生成新的配送计划。信息获取过程如下：MC用于获取顾客需求量和需求点位置信息，ITS用于获取实时交通道路信息，车辆使用GPS进行定位，GIS用于获取任意两个顾客的实际距离。根据以上实时信息，每次有动态事件发生，配送中心生成新的配送路径方案，其指令通过GSM传达给车辆司机。

关于动态车辆路径问题的研究在近10年取得了一定的进展。谢秉磊和郭耀煌[1]对动态车辆路径问题的研究进行了综述，并对该问题的发展前景进行了展望。针对在配送过程中有事先未知位置的新顾客出现的情形，Branke[2]提出了以最大概率将新顾客整合到原配送方案的等待策略。Potvin[3]针对考虑顾客实时需求和动态行驶时间的动态车辆路径问题，比较了不同的调度策略。针对动态网络环境下的车辆路径问题，王江晴[4]提出了一种实时路径评估模型，用于找出实时最短路径，在此基础之上构造了一个改进的Dijkstra算法，实现对行驶线路的不断调整。Du等[5]以牛奶配送为应用背景，提出车辆实时调度中采用2-Exchange改进法则用于配送线路内部的改进十分迅速有效。刘霞[6]研究了带时间窗的动态车辆路径问题，使用插入法构造初始解，使用重定位法、节点交换法、2-opt法和Or-opt法4种局部搜索方法的不同组合完成对初始解的改进。刘士新[7]设计了在动态环境下的车辆路径问题，提出一种导向局部搜索算法，算法对初始解中各车辆配送路线的顾客服务顺序进行动态改进。针对具有模糊预约时间的动态车辆路径问题，张建勇[8]提出了在新顾客出现时的一种插入启发式算法，确保顾客综合满意度最大。针对出现新需求的情况，Attanasio等[9,10]提出了接受或拒绝新订单的策略。郎茂祥[11]考虑车辆故障和允许多次配送的情况，提出了包括制定整体计划和实时局部优化的两阶段策略，分别采用禁忌搜索算法和局部搜索算法进行求解。针对配送车辆在配送途中出现故障的情形，Li[12]提出了一种拉格朗日松弛插入算法安排其他配送车辆完成故障车辆尚未完成的配送任务。王旭坪[13]等从干扰管理的角度，提出了解决配送过程中出现动态信息的方法。陈森[14]针对路网结构变动和需求随机双重不确定因素的动态车辆路径问题，设计了加速自适应遗传算法进行求解。针对带时间窗动态车辆路径问题，王君[15]通过定义紧急顾客，提出基于紧急顾客插入的重复优化方法、分批处理的方法或上述两种方法的的混合三种应对策略。

对于动态车辆路径问题，目前相关研究多采用插入新需求点和调整部分线路的局部优化方法，尽量减少原有配送线路的变动程度。针对可能发生的动态事件，通常只选取其中的一种或两种情形作为考虑对象。

针对现行研究存在的上述问题，本文考虑配送过程中可能发生的多种动态事件，在每次动态信息更新后在原有配送方案基础上对剩余尚未配送的顾客需求点进行全局优化。提出了一种能够即时处理各种动态信息的车辆实时调度方法，考虑了顾客接收货物的时间窗限制和车辆超出最大距离的附加成本。通过实时收集顾客需求信息、监测车辆运行情况，对已经安排好的车辆路径进行即时调整或重新安排车辆所需服务的顾客需求点，实现配送路径的实时优化调整。

2 实时车辆调度问题描述与模型构建

2.1 建模假设与符号说明

本文研究的动态车辆路径问题，可定义如下：在保证每个顾客的需求被满足，且不超过配送车辆的最大配送量，考虑车辆超出最大行驶距离和违反时间窗限制的附加成本的情况下，考虑配送过程中实时变化的信息（需求点增减、需求量变化、道路交通中断、配送车辆故障），每当有动态事件发生时应该如何重新安排车辆的行驶路线，目标是使整个配送周期的车辆配送总成本最小。

本文假设配送中心有一定数量的配送车辆，车辆载重量均为Q，所有顾客的货物需求量均小于配送车辆的最大装载能力，车辆由配送中心出发，完成配送任务后要返回配送中心，方案计划安排的车辆数为m，平均车速为v.c为单位距离运输成本，c0为多派出一辆车的固定成本。车辆每日最大行驶距离为L，超出最大行驶距离后的惩罚系数（即每公里需附加支付给司机的费用）为pl，违反时间窗约束的惩罚系数为p1、p2.

每当有动态事件发生时，更新所有相关信息，包括：已经完成服务的顾客集合I1={1,2，…，n′}；尚未服务的顾客集合I2={1,2，…，n}，顾客i的货物需求量qi、服务时间si及顾客位置，i∈I2，顾客i要求货物最好在时间窗[ETi,LTi]内送达，最差不得超出[ai,bi]的送货时间范围；尚未服务和已服务的所有顾客集合I={1,2，…，n′，…，n′+n}；正在执行任务车辆集合H={1,2，…，h}，各车的位置和状态（车辆是否发生故障），各车在该时刻已完成的货物配送量Qk和已行驶的距离Lk,k∈H；当前所有节点集合（尚未服务的顾客、虚拟顾客、配送中心）N={0,1，…，n，…，n+h}，任意两节点距离dij，及现有节点间各路段交通状况（道路交通中断时dij取无限大），i,j∈N；尚未服务的顾客和虚拟顾客的集合D={1，…，n，…，n+h}。

动态事件发生时，对尚未服务的顾客重新编号1,2，…，n，虚拟顾客编号n+1,n+2，…，n+h，配送中心编号仍为0，将正在执行任务的车辆（亦即该路径）与各自虚拟顾客n+1,n+2，…，n+h对应编号为1,2，…，h，从配送中心出发的车辆顺次编号为h+1,h+2，…，m．配送车辆集合M={1,2，…，h，…，m}。

决策变量xijk表示车辆k经过路径（i,j），有

车辆k到达顾客i的时间为TAi，离开时间为TLi．显然有，，递推可得，而TLi=TAi+si.

2.2 问题分析与转化

根据配送开始之前的已知信息，按照静态车辆路径问题的方法进行求解，所得即为初始配送方案。

配送开始之后有任何一种动态事件发生时，部分车辆正在配送途中进行配送。此时，需更新所有相关信息进行重新调度。该时刻点的路径安排问题可视为多车型的混合式车辆路径问题，原因如下：

(1)在配送中心尚未出发车辆的货物配送量是Q吨，其最大行驶距离为L；在配送途中的车辆已经完成Qk吨货物配送量，车上剩余Q-Qk吨货物配送量，其最大行驶距离为L-Lk．因此，在配送中心尚未出发的车辆和在配送途中的车辆可以看作不同的车型。

(2)在配送中心即将出发的车辆最终会回到配送中心，其行驶路线是闭合回路；在配送途中的车辆此时不在配送中心，相当于从该时刻点该车辆所在途中位置出发，最终返回配送中心，其行驶路线是开放式的路径，而不是闭合回路。因此，在重新调度时，可以将该问题看作是包含封闭式和开放式车辆路径问题的混合式车辆路径问题。

进一步将多车型的混合式车辆路径问题转化为静态单车型车辆路径问题，转化方法如下：

(1)将在配送途中正在进行配送的车辆k当前所在的位置设置一个虚拟顾客，其需求量为Qk，该虚拟顾客与配送中心的距离为Lk.

(2)在配送途中正在进行配送的车辆必须首先服务其对应的虚拟顾客。

2.3 数学模型

根据上述求解思路，本文提出的动态车辆路径问题模型建立如下。

目标函数：

其中，

约束条件：

模型中，式（1）表示问题的目标函数配送总成本最小，包括车辆的运输成本、车辆启用的固定成本、超出最大行驶距离附加成本（2）和违反时间窗限制的惩罚成本（3）；约束（4）保证每辆配送车辆均不超过其最大载量能力；约束（5）、约束（6）确保每个顾客只能被分配到一条路径上，即只被服务一次；约束（7）保证每一条路径上，离开每个节点的车辆数等于进入该节点的车辆数；约束（8）确保所有车辆的起、终点都在配送中心；约束（9）表示每辆当前正在执行任务的车辆必须首先服务其对应的虚拟顾客，从而使配送的路径转化为简单圈；约束（10）限制车辆行驶路径轨为简单圈，避免子回路的产生。式（11）为到达时间的非负性约束。

3 混合遗传算法设计

3.1 实时调度的整体流程

步骤1：数据初始化。开始时间为0，全部车辆起始位置在配送中心。根据现有的相关信息，利用混合遗传算法生成初始配送方案。

步骤2：车辆司机严格按照调度中心传达的配送线路行驶。

步骤3：判断是否已经完成所有配送任务或达到最长工作时间。若是，结束任务，车辆返回配送中心；否则，转步骤4。

步骤4：发生动态事件时，更新相关信息，得到一组新的需求节点和需求量，在途车辆状态、位置的集合，以及当前各路段交通状况的相关信息。

步骤5：调度中心根据最新雅息对配送车辆的行车路线进行重新安排，并将新的行车路线即时传达给配送车辆司机，下转步骤2。

3.2 混合遗传算法步骤

根据模型的结构特点以及决策变量的可行域，本文设计了结合局部搜索思想的混合遗传算法，在每次信息更新后重新对配送路线进行求解，从而实现实时调度。混合遗传算法按以下步骤进行：

Step1：编码，生成初始种群。采用需求点直接排列的编码方法，用一个染色体表示所有尚未服务的需求点的配送顺序，即由尚未服务的顾客编号1～n构成一个实数串。随机产生未被访问过的需求点序列，按顺序逐一将每个需求点加入到当前配送路线中。检验是否满足车辆载重限制，若满足，则将该需求点加入到当前配送路线中；若不满足，则将其加入到下一条配送路线，如图1所示。

重复上述过程得到N条染色体。

Step2：计算个体适应度。P=1/（Z+Gpw）。式中Z为目标函数值，G为配送路径条数与配送中心的车辆总台数之差（若配送路径条数<车辆总台数，则取G=0，表示该个体对应一个可行解；否则，G>0，表示该个体对应一个不可行解），可将G看成该个体对应的配送路径方案的不可行路径条数，设对每条不可行路径的惩罚权重为pw．若适应度值满足优化准则，满足转step8，否则转step4。

Step3：选择再生个体。采用轮盘赌选择具有较高适应度的个体。保留当前子代的最优解，并保持子代的群体个数与种群个体数相同。

Step4：交叉方法采用类改进的OX法实施交叉操作。操作方法说明如下：选择两条父代染色体，随机选择两个基因交叉点，在两个父代个体前分别加入异方双亲的交叉区域，顺次删除与交叉区域重复的基因，得到子代染色体。交叉操作示意图如图2。

Step5：变异。对子代进行两点交换操作。交换前后进行适应度计算，如果其适应度比之前好，那么采用变异后的值，如果较差，则再进行一次随机变异。

Step6：判断是否达到预先设定终止进化代数，满足转下一步，否则返回Step2。

Step7：输出最优解，算法停止。

4 算例设计与结果分析

4.1 算例设计

某城市配送中心位置坐标为（112,88）。共有15台配送车辆，拥有若干个位置已知的潜在需求点。运输成本c=1元/公里，多派出一辆车的固定成本c0=100元，车辆最大货物配送量Q=8吨，车辆每日最大行驶距离L=250公里，超出最大行驶距离后每公里需附加支付给司机的费用pl=1元/公里，p0=20元，p1=p2=50元/小时，ai=ETi-2,bi=LTi+2,A=10000元，平均车速v=50公里/时，粗略将需求量（吨）的1/3记为该需求点的服务时间（小时）。

在配送开始前有8个货物配送任务，各个顾客的需求情况如表1所示。

4.2 对比策略

将本文所提出的实时调度方法与传统的静态调度方法进行对比实验。

传统的静态调度方法是指所有配送车辆均按照配送开始前的初始配送方案进行配送，配送顺序和配送量均不作任何变动。对于配送过程中可能出现的各种动态情形，采取如下方式进行处理：

(1)在配送过程中，对于新增需求点和需求量，从配送中心另外派出车辆进行配送，调度方法与静态车辆路径问题相同。

(2)对于取消订单的需求点，配送车辆直接将其略过，对下一顾客进行配送。

(3)对于在途中发生故障的车辆，从配送中心另外派出车辆按照顾客点顺序依次完成该车未完成的配送任务。

(4)对于两需求点间发生交通中断的情形，该配送车辆直接对原路线的下一需求点进行配送，发生交通中断而无法到达的需求点由新派出的车辆进行配送，调度方法与静态车辆路径问题相同。

4.3 结果分析

(1）初始配送线路的构建

使用混合遗传算法进行求解，得到初始配送线路。配送中心需派出3辆车，配送路线分别为：0-1-4-5-0,0-8-22-0,0-17-16-15-0。

(2）实时信息下的线路优化

(1)情形1:

T1=1时20分，发生如下动态事件：老顾客4、22分别新增需求0.5吨，老顾客5取消订单，出现新顾客6、7、10、11、19、28、29。此时，尚未服务的顾客需求见下表。

对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表3。

若使用传统的静态调度方法，可以得到如下配送方案。

对比表3和表4可以得出，如本算例在需求点和需求量发生变动的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本，在该算例中可以有效降低157.8元，高达原配送成本的10.4%.

(2)情形2:

T2=2时，发生如下动态事件：车辆2在行驶途中发生故障，短时间内无法修好；顾客15、16之间的交通中断。此时，还剩下顾客4、5、15、22未被服务。

对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表5。

若使用传统的静态调度方法，可以得到如下配送方案。

对比表5和表6可以得出，如本算例在车辆发生故障和部分顾客间出现交通中断的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本130.7元，降低14.6%，显示了本文动态车辆调度方法的有效性。

5 结论

对于需要具备快速响应能力的城市配送问题，本文通过引入虚拟顾客的概念，将实时信息下的动态车辆路径问题转化为经典的静态车辆路径问题。借助GIS、GPS、ITS等技术工具获取实时信息，解决了四种动态事件情形下的配送线路实时优化调度。运用所提出的混合遗传算法求解模型，通过算例测试，与传统的非实时配送方案进行对比，得出该调度方法可以有效地找到实时最短路径、降低配送成本。

物流配送车辆优化调度问题概述 篇3

配送是以用户需求为前提,对货物进行挑选、包装和分配等一系列工作,并将其送至指定地点的活动。配送是物流活动的核心环节,需要完成货物的包装、保管、运输和装卸等多项任务。配送的基本要求是保证货物的种类和数量没有差错,在此基础上保证能够按时送达客户。在实现这两个保证后,力争寻求到更加节约成本且更为快捷的配送方案,以实现利益的最大化。而在整个物流配送环节中车辆调度问题最为重要,与经济效益密切相关。

从1959年首次提出物流配送车辆优化调度问题直至发展到今天,物流配送行业一直致力于在满足一定约束条件下(包括用户需求和现实因素的限制等),选取最为合适的行车路线,争取最大面积覆盖取送货点,优化各项指标,最终实现效益的不断攀升。

2 车辆优化调度问题概述

车辆优化调度问题根据时间特征的差异可分为车辆调度问题VSP(Vehicle Scheduling Problem)、车辆路径规划问题VRP(Vehicle Routing Problem)以及有时间窗的车辆路径问题VRPTW(Vehicle Routing Problem with Time Windows)。其中VSP问题侧重于考虑时间上的要求来安排运输线路;VRP问题不考虑时间因素,仅从空间上对问题进行优化,目的在于令安排的路线更加合理;此外,由于VRP问题的不断发展,在原本根据空间来安排路径的基础上,加上时间上的排程考虑,便成为有时间窗的车辆路径问题VRPTW,特点在于在车辆途程问题之中加入时间窗的限制。

也可进行如下分类:

(1)按送货计划安排分为纯装问题、纯卸问题和装卸混合的问题。区别在于安排纯装问题和纯卸问题的车辆允许在所有任务点装货或卸货。而装卸混合问题比较复杂,装货和卸货可能同时进行,并没有严格界定。

(2)按车辆的装载货物量分为满载问题和非满载问题。安排满载的车辆完成任务时可能需要多辆车,而安排非满载的车辆完成任务时,多项任务仅需一辆车就能完成。

(3)按车辆类型分为单车型问题和多车型问题。单车型要求完成此次任务的所有车辆,其容量完全相同,而多车型并没有此要求,可以搭配安排。

(4)按优化指标多少分为单目标优化问题和多目标优化问题。单目标优化问题仅要求一项指标最优,通常这项指标是该次任务最为重要的指标,而多目标优化问题将考核目标范围扩大,要求多项指标最优或较优,如既要求路途短,又要求运费少。

(5)按时间窗要求分为硬时间窗问题、软时间窗问题。硬时间窗要求车辆必须完全遵照时间安排,早到必须等待,而晚到则拒收。而软时间窗相对灵活一些,可以不在时窗内到

3 车辆优化调度问题研究

车辆优化调度问题可通过精确算法和启发式算法来进行求解。精确算法是根据问题建立数学模型,然后进行求解,具体方法都有割平面法、线性规划法、动态规划法等,精确算法由于设计过于理想,并不具有普遍适用性。启发式算法结合直观情况和经验,是一种逐步逼近最优解的算法,具体方法有构造算法、神经网络法、遗传算法等,启发式算法更为接近实际生活情况,适用范围广泛,正是我们研究的重点所在。

在此介绍几种常用的优化算法:

3.1 遗传算法

J.Holland教授于1975年首次提出遗传算法(Genetic Algorithm,GA),遗传算法源于物种进化的自然选择理论,结合物种进化过程中适者生存规则以及染色体中随机信息的交换,发展形成的一种智能算法。遗传算法的基本思想是:从群体中选择较为适应环境的个体用于繁殖下一代,对选中个体进行交叉、变异等操作,以适应度为选择原则,通过算法的迭代选取最优个体。当最优个体的适应度不再变化时迭代结束,得到全局最优解。遗传算法广泛应用于多项领域,属于智能计算的关键技术。

优点是具有鲁棒性,全局搜索能力强,耗时较短,但是不能保证每次搜索结果一样。

3.2 模拟退火算法

N.Metropolis于1953年首次提出模拟退火算法(Simulated Annealing,SA),模拟退火算法的基本思想是:首先,给定一个初始状态,并设定初始温度和降温次数,同时在邻域范围求出另一个解,结合控制参数选择接受或舍弃,经过反复实验后,求得参数控制下的相对最优解;下一步,构造降温函数,不断减小控制参数的值直至为0,此时获得的解即为全局最优解。前半部分是通过加热增加物体能量;后半部分是通过降温来减少物体的能量。对照数学模型,所构造的目标函数就是物体的能量,故求最优解的过程就是求能量最低态的过程。

优点是有很强的全局搜索能力,但是由于允许移动到较差的解,所以会出现接受目标值不好的状态,仅产生局部最优解,导致求得全局最优解要花费较长时间。此外模拟退火的有效性与邻域的选择相关,若邻域的设计范围合理,算法将更为优越,反之,会影响获得的结果。

3.3 蚁群算法

M.Dorigo于1992年首次提出蚁群算法(Ant Colony Algorithm,ACA),蚁群算法源于蚁群在觅食时发现最短路径的行为,蚁群通过寻找信息素浓度最高的路径,从而找到最佳路径,蚁群算法是一种模拟进化算法。蚁群算法的基本思想是:首先,将多只蚂蚁分别放在不同的初始点处,设定顶点也置于当前解集中,蚂蚁从初始点开始转移,直到所有的点都已存在于解集中,得到各只蚂蚁的适应度,记录下当前最优解;然后更新信息素,迭代结束后,求出种群进化后的最优解,便得到问题的最优解。

优点是求解结果不依赖于初始线路,且不需要人为参与调整,设置较为简单,但需要不断调整变量,过程繁琐,任务量大。

4 当前研究中存在的问题

当前对于物流配送车辆优化调度问题的研究,模型设计比较简单,而且将影响因素孤立开来,使得构造的模型与现实复杂的情况出入较大。其次,典型模型的设计与实际情况不符,如典型模型默认是集货送货一体化的问题。实际上,大部分物流公司的业务是集货任务、送货任务、集送一体化任务混合在一起的,在物流配送中需要综合考虑,统一安排车辆。另外,在模型的设计中并未考虑到一些突发情况,过于公式化,导致在实际应用中比较局限。

5 车辆优化调度问题研究展望

针对当前研究中存在的问题,要想把研究真正与实际相结合,更具有应用价值,应该注重对研究问题的描述,建立与实际情况相符合的模型。其次,鉴于道路交通状况对调度的影响越来越大,将实时交通状况与车辆调度问题相结合是十分有必要的。

物流业和配送业近几年在我国迅速崛起,车辆优化调度问题也日益重要。但是由于我国在这方面起步晚,发展速度缓慢,无法满足日益增长的需求。同时对于通用理论的研究较少,对于应用性研究也过于局限。因此,有必要将研究的部分重心转移到通用性好、运算速度快且精度高的优良算法上来,以缩短存在的技术差距,健全快速发展的物流业,促进经济的进一步发展。

参考文献

[1]张强,荆刚,陈建岭.车辆路线问题研究现状及发展方向[J].交通科技,2004,(1):60-62.

[2]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法[J].中国公路学报,2006,19,(4).

[3]唐小明,郭晓汾.基于物流配送服务水平多指标的车辆模糊优化调度[J].西安工业学院学报,2005,25,(3).

[4]骆义,谢新连.物流配送车辆调度优化研究[J].大连海事大学,2003,(3):7-12.

[5]宋华,胡左浩.现代物流与供应链管理[M].北京:经济管理出版社,2000,11,4.

城市配送车辆 篇4

在竞争日益激烈的现代商业信息社会,企业只有以市场为核心去适应不断变化的环境并及时对市场做出反应,才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标。合理使用调度运输工具,优化运输路线,降低企业物流成本,是物流管理的重要功能。由于对物流管理中的车辆调度问题的研究对社会经济发展具有举足轻重的作用。因此,国内外学术界对物流运输系统的调度优化问题十分关注。配送是物流系统的一个重要环节,配送业务中,配送车辆调度问题的涉及面广,是配送系统优化的关键,具有很大的分析价值。本文正是基于这个原因才对车辆调度问题进行研究。

2 车辆调度问题的概述

物流配送车辆优化调度问题最早是由Dautzig和Ramser于1959年首次提出的,称之为Vehicle Routing Problem(简称VRP)[1]。

VRP问题一般定义为:对一系列给定的顾客(取货点或送货点),确定适当的配送车辆行驶路线,使其从配送中心出发,有序地通过它们,最后返回配送中心,并在满足一定的约束条件下(如车辆容量限制、顾客需求量、交发货时间等),达到一定的目标(如路程最短、费用最少等)。

车辆的优化调度问题主要探讨:组织的行车路线,能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下,有序地通过一系列供应点或需求点,达到诸如路程最短、费用最小,耗费时间尽量少等目的[2,3]。

自VRP被提出之后,人们在解决VRP问题的时候,综合考虑多方面的因素,如有无时间限制、纯装纯卸或是混合装卸、是满载或是非满载、车型是单车型或是多车型、是单配送中心或是多配送中心以及车辆配送完是不是必须返回原始配送中心等。

2.1 车辆调度问题的分类[4]

车辆调度问题可以细分为VSP(Vehicle Scheduling Problem,即车辆调度问题)和MTSP(Multiple Traveling Salesman Problem,即多旅行商问题)。但是按照大多数人的习惯,对这几类问题不做严格细分,仍统称为车辆调度问题(即VRP问题)。

车辆调度问题可以根据不同性质划分为以下几类:

有无时间限制问题,即我们所说的有时间窗车辆调度问题和无时限车辆调度问题,是指配送货是否必须在一定的时间限制内完成。对有时间窗的车辆调度问题又可以分为硬时间窗问题和软时间窗问题。而硬时间窗问题是指运输任务必须在规定的时间内完成;软时间窗问题是指任务不一定非得在规定的时间内完成,但是超过规定的时间,则会受到一定的处罚。

纯装问题或纯卸问题,即车辆在所有任务点装货或卸货,即集货或送货问题;而装卸混合问题,则是指每项任务有不同的装货点和卸货点,即集货、送货一体化问题。

满载问题,即货运量不小于车辆容量,完成一项任务需要不只一辆车;而非满载问题,则是指货运量小于车辆容量,多项任务用一辆车。

单配送中心问题和多配送中心的问题,则是考虑客户与配送中的距离长短,以便节约企业运输成本、提高运输效率。

单车型问题即所有车辆容量相同,而多车型问题即执行任务的车辆容量不全相同。

车辆开放问题即车辆可以不返回其发出车场,而车辆封闭问题是指车辆必须返回其发出车场。

综上所述,车辆调度问题涉及的内容较广,包括中国邮递员问题、旅行商问题、指定两点之间的最短距离以及任意两点之间的最短距离等问题,所以研究起来较复杂。

2.2 VRP研究动态及水平

车辆调度问题自被提出来以后,近二十年来,无论是国外还是国内,它都是一个发展活跃的一个领域。在国外,VRP问题已经广泛的应用于实际生活,如邮局的邮件递送业务、超市的商品供应、牛奶站的牛奶送达业务、工业产品的传输、快递公司的运输安排,并取得了很大的经济效益。

VRP问题自从被提出以来,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。在经典VRP的基础上,车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态,包括TSP(可看作VRP的一个特例,即当VRP只包括一条路径,且没有能力约束时就成为TSP)、带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW)、,随机需求车辆路径问题(Vehicle Routing problem with Stoehasti Demand,VRPSD)、动态车辆路径问题(Dynamic vehicle Routing Problems,DVRP)等[5,6]。早在60年代Clarke和Wright就提出的节约法(Saving Method)。1962年,Balinski等人首先提出VRP的集分割,直接考虑可行解集合,在此基础上进行优化,建立了最简单的VRP模型。1971年,Eifon等人提出将动态规划法用于固定车辆数的VRP,通过递归方法求解。其后,Christofields提出了状态空间松弛,极大地减少了状态数量。1974年,Gillet和Miller提出的扫描法(Sweeping Method)。1981年,Christofides等人提出了k度中心树和相关算法,对固定车辆数m的m一TSP进行k度中心树松弛。后来,M LFisher对这种方法做了进一步改进,可求解有134个客户的VRP。1991年,Gendrean等人[8],将禁忌搜索方法应用于VRP。其后E Tailiard等人[9]。通过按角度和路径重心对原问题的空间进行分割,再用禁忌搜索结合模拟退火对子问题求解,实现了对问题求解的并行化。1996年,J.Lawrence[10]将遗传算法用于VRP的研究,并可有效求解带时间窗口的VRP。

此外,国外从实用化角度开展的研究也比较多,研究者将模型和算法方面取得的进展应用于很多具体问题。也由此诞生了一些为企业车辆路径提供服务的专业化公司,开发了各具特色的车辆路径软件,比较著名的有:美国ES班公司的Aiclogisties系统,Roadnet科技公司的Roadnet5000系统,Routesmart科技公司的Routesmart系统,Optrak软件公司的OPtrak系统,IBM的VSPX系统,美孚的HPCAD系统,另外还有日本富士通的VSS系统等。

国内VRP的研究起步较晚,国内也有一些对车辆调度进行的研究。李大卫等以TSP的最近距离启发式算法为基础,通过设置评价函数来处理时间窗约束,求解了简单的VRP[7]。张震针对单车场满载问题,提出了考虑运输行程约束的优化方法。蔡延光等应用并行禁忌搜索算法和模拟退火算法对满载问题进行了求解[20]。刘浩等用模拟退火算法求解了两车型随机需求的VRP[11]。张涛等用禁忌搜索算法和遗传算法的混合策略求解了VRP[20]。王莉用启发式算法求解了有时限的VRP[13]。袁健等用神经网络法求解了VRP[14]。姜大立、李大卫分别用遗传算法求解了无时限和有时限的物流车辆调度问题。近年来,郭耀煌、李军、谢秉磊等对物流车辆调度问题进行了较为深入的研究,提出了多种求解算法。周双贵对物流车辆调度问题的模型和求解方法也进行了较为深入的研究[19]。

2.3 车辆调度的目标

车辆调度的目标是以尽量少的路径距离、费用消耗、时间消耗和所需车辆数来可靠地完成汽车调度和货物配送任务。

3 车辆调度问题的研究方法

车辆调度问题的求解算法包括精确算法和启发式算法两个类别。由于车辆调度问题是NP-hard问题,存在高效的精确算法的可能性不大。因此,学者们主要将精力集中在构造高质量的启发式算法上。

3.1 精确算法

精确算法是指可以求出其最优解的算法,主要有:

1) 分枝定界法

此方法是一种隐枚举法或部分枚举法,它不是一种有效算法,是枚举法基础上的改进,是求解整数规划的较好方法。Kolen曾利用此方法求解有时间窗约束的车辆巡回问题,其实验的节点数范围为6~15。当节点数为6时,计算机演算所花费的时间大约1分钟,当节点数扩大至12时,计算机有内存不足的现象产生,所以分枝定界法比较适用于求解小型整数规划问题。Held和Karp指出分枝定界法的求解效率与其界限设定的宽紧有极大的关系,所以分枝定界法比较适用于求解小型问题。

2) 割平面法

此方法与分枝界限法类似,也是在求解与整数规划相对应的线性规划上,不断地增加新的约束,也就是另外加入线性约束条件,以切掉对应于非整数规划的所有可行解的集合,以使问题可达到整数线性规划求解的形式,从而获得最优解。求解时间过长,不适用于大规模问题。

3) 动态规划法

该算法解题的基本思路是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。因其复杂性在于各阶段决策之间的相互联系,而且计算时间与计算机内存空间均随变量的增加而里指数增加.所以虽然此方法可求得最优解,但仅适用于较小规模的寻优问题。第一个VRPTW最优化算法是Kolen等在1987年提出的动态规划算法。

精确算法的计算量随着车辆优化问题规模的增大呈指数增长,如当停车卸货点的数目超过20个时,采用一般的精确算法求解最短配送路径的时间在几个小时以上。所以精确算法不适合于求解大规模的车辆路径优化问题。

3.2 启发式算法

3.2.1 传统启发式算法

传统的启发式算法在求解VRPTW问题时通常是从初始解出发,以邻域搜索的方式实现解的改进,并在较短的时间内获得一个可以接受的解。

1) 节约算法(Saving Method)

算法思想是将每条路线只含一个配送点的n条路线作为初始解,其中,每条路线中第一个和最后一个配送点分别称为路线的起点和终点。考察一条路线的起点与另一条路线的终点相连合并成新的一条路线。如果合并后的路线满足约束条件(车辆容量、时间窗),则认为这样的合并是可行的,并将合并的节约值定义为连接这两条路线的边的节约值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并时,算法结束。此方法的优点是可提高车辆的利用率。

2) 邻接算法(Nearest-Neighbor)

邻接算法是一种序列构造路线法。算法从一条只含一个配送点的路线出发(通常取“距离”配送中心最近的点)。在未分配点中筛选出可加入点(未分配点且可行),并从可加入点中选取一个点作为当前路线的终点,使得路线的成本最小。如此不断对路线进行扩充,直到路线不存在可加入点为止。这时,如果所有点均已分配,则算法结束;否则,生成一条新的初始路线,重复前面的路线扩充程序。

3) 插入算法

插入法是结合邻接算法与节约算法的观念,依序将顾客点插入路径中以构建配送路线。它的流程与邻接算法相似,也是从初始路线出发,序列构造路线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。

4) 扫除算法

扫除算法是一种“先分组后路线”的算法。所谓分组,即指分派给每辆车一组点。一种简单的分组方法是将以车站为原点的坐标平面划分为多个扇形区域,并初步将每个扇形区域的点分派给一辆车。而所谓的“路线”,是指在每个区域内,采用扫除法选择未分配点,然后应用插入算法扩充路线。如果在进行了一次“分组——路线”的路线构造后,还存在未分配点,则再进入“分组——路线”程序。如此反复,直到所有点均已分配为止。

3.2.2 现代启发式算法

相对于传统启发式算法,现代启发式算法不要求在每次迭代中均沿目标值下降方向,而允许在算法中适当接受目标值有所上升甚至不可行的解,其目的是能够跳出局部搜索邻域。

1) 禁忌搜索算法(Tabu Search,TS)

禁忌搜索算法是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的局部最优点,并在后面的搜索中,根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。

2) 遗传算法(Genetic Algorithms,GA)

遗传算法是借用适者生存规律进行局部搜索改进的一类算法。该算法通过染色体的配对和变异过程实现种群的进化,每一次进化则对应解的一次迭代。当迭代次数达到最大次数限制或群体中的个体无显著差异时,迭代终止。

3) 模拟退火算法(Simulated Annealing,SA)

1996年,Chiang和Russell提出VRPTW问题的模拟退火算法。模拟退火算法实际上是一种随机松弛技巧,它模拟了退火过程。在搜索的初始阶段,算法跳向远点,随着时间的延伸或“降温”,跳跃幅度逐渐减小,最终转向局部搜索下降方法。

4) 蚁群算法(Ant Colony Optimization,ACO)

蚁群算法模拟了蚁群搜索食物的行为。在寻找食物时,蚂蚁会在它所经过的路径通过排放一种外激素(pheromone,在算法中称为信息素)作出标记,排放的量则根据路径长度和食物的等级决定。这些外激素为其它蚂蚁提供信息,并吸引他们前去搬运食物。算法中,首先构造两组相互协作的人工蚁群,其中第一个蚁群用于最小化车辆数,第二个蚁群用于最小化总路长。并以共用解的方式建立协作关系。

4 各种车辆调度优化算法的比较分析

大家知道,各种优化算法都有其一定的不足之处,不然的话也就不会有这么多的优化算法了。各种优化在一定时期、一定的情况下都有各自的优点,都有解决某一类问题的优越性,但随着发展的需要,对优化方法的要求也就越来越高了。下面对上面所述几种优化方法进行比较分析,通过表格的形式来展现各自的特点。

通过表1我们可以看出精确式优化算法求解是最优解,但只适用于小规模的VRP问题,而不适用于求解复杂的VRP问题,求解复杂的VRP问题时费时又费力,且难以实现。

物流配送车辆调度问题算法综述 篇5

无论是对于物流中心,还是第三方物流公司,物流配送运输车辆的调度都是工作重点,通过减少运输成本、节约运输时间,从而提高经济效益。

1 配送车辆调度优化问题的分类

车辆路径调度问题的一般定义为:对一系列发货点和收货点,组织适当的行车路线,使车辆有序通过它们,在满足一定的约束条件下(如货物需求量、车载量、交发货时间、行车里程、时间限制,路线约束等),达到一定目标最优化(如路程最小、运费最少、时间准时、车辆较少等)。

1.1 按时间因素分类

配送车辆调度优化问题可以简单地分为三类,第一类问题称为车辆路径规划问题(Vehicle Routing Problems,VRP),VRP问题关注为车辆安排合理、高效益的线路,仅是在空间上对问题进行优化,而不考虑时间因素。第二类问题称为车辆调度问题(Vehicle Scheduling Problems,VSP),VSP问题也关注合理、高效安排车辆行车路线,所不同的是,VSP问题考虑的是在满足时间要求的前提下实现最优调度。第三类问题称为路径和调度的混合问题(Vehicle Routing And Scheduling Problems,VRP&VSP),就是将前两类问题综合考虑的问题。而目前也有学者不区分VRP和VSP问题,而是将考虑时间因素的VSP问题称为VRPTW(Vehicle Routing Problem with Time Windows)问题。

1.2 按性质分类

车辆优化调度问题可以根据其不同的性质分为以下几类:

(1)按运输任务可以分为纯装问题、纯卸问题和装卸混合问题。纯装问题就是每一项任务只有装货点,是一个集货的过程。纯卸问题是指每一项任务只有卸货点,是一个送货的过程。而装卸混合问题是指每一项任务有不同的装货点和卸货点,是集货、送货一体化的过程。

(2)按车辆载货情况可以分为满载问题和非满载问题。满载问题是指一次任务的货运量多于车辆的最大容量,而非满载问题是指一次任务的货运量不多于车辆的最大容量。

(3)按车辆类型分为单车型问题和多车型问题。单车型问题指所有车辆的容量都给定同一值,多车型问题指所有车辆的容量都给定不同值。

(4)按车场的数量可以分多车场和单车场问题。因为多车场问题可以转化为单车场问题,而且通常一个车场(仓库)都会有固定的服务对象。根据传统的处理方法,在将多车场问题转化为单车场问题的过程中,先设一个虚拟车场,将所有配送点和实际车场都看作虚拟车场的配送点,这样就转化为单车场问题了。所以这里的算法只考虑单车场问题。

(5)按车辆是否返回车场可以分为车辆开放问题和车辆封闭问题。车辆开放问题是指在车辆开出车场以后不返回车场。而车辆封闭问题是指在车辆开出车场以后返回其发出车场。

(6)按优化目标可以分为单目标优化问题和多目标优化问题。单目标优化问题是指目标函数只要求一项指标最优,如要求运输路径最短。多目标优化问题是指目标函数要求多项指标最优或较优,如同时要求运输费用最少和运输路径最短。

(7)按货物种类可分为同种货物优化调度和多种货物优化调度。同种货物优化调度是指要运输的货物的种类只有一种。多种货物优化调度是指要运输的货物的种类多于一种,所以车辆装载时要考虑一些种类的货物不能同时装配运输。

(8)按有无休息时间要求可分为有休息时间的优化调度问题和无休息时间优化的调度问题。

(9)按有需求点有无时间窗要求,可分为无时间窗问题、硬时间窗问题、软时间窗问题。硬时间窗问题指车辆必须在时间窗内到达,早到则等待,晚到则拒收。软时间窗问题指车辆不一定要在时间窗内到达,但是在时间窗外到达必须受到惩罚。

建立车辆调度问题模型如下:

目标函数:a.单目标,b.多目标(目标函数包括总费用最小、总里程最小、休息时间最大、惩罚最少等)

约束条件:a.时间约束(无时间窗、硬时间窗、软时间窗)

b.距离约束(无距离限制、硬距离限制、软距离限制)

c.行车路线约束(无相交性限制、顶点不相交)

d.流量限制(无流量限制、边限制、顶点限制)

e.满载限制(满载,非满载)

f.其它要求

2 物流配送车辆调度算法综述

在求解车辆优化调度问题时,可以将问题归类为几个简单的组合优化基本原型,如旅行商问题(TSP)、最短路径问题、最小费用流问题、中国邮递员问题等,再用相关的理论和方法进行求解,得到模型最优解或较优解。

一般求解VRP问题主要可分两大类,一类是精确算法;一类是启发式算法。精确算法主要有分支定界法、割平面法、线性规划法、动态规划法等,它的主要思想是根据问题先建立具体的数学模型,然后利用数学方法进行求解。启发式算法主要有构造法、人工智能法等,如构造算法、两阶段法、神经网络法、遗传算法等,它的主要思想是根据直观和经验开发出能朝着最优解方向搜索或靠近的算法。

由于车辆优化调度问题的规模大、复杂性强,而各种计算和实验得出,智能算法在求解这类问题时有较强的可行性,所以这里仅探讨智能算法求解车辆优化调度问题。

2.1 遗传算法

遗传算法(Genetic Algorithm,GA)由美国J.Holland和他的学生于1975年建立并发展起来的。遗传算法是根据自然选择和遗传理论,将生物进化过程中适者生存规则与同一群染色体的随机信息交换相结合的智能算法。遗传算法的基本思想是:首先,通过一组编码,将问题在表现型与基因型之间转换,并形成初始种群,计算种群中个体的适应度;其次,设计遗传算子(包括复制、交叉、变异),从对已产生的解(“父代”)中根据交叉率,从部分个体中选取部分基因,按某种组合形成新的个体;根据变异率,从部分个体中选取部分基本变异,产生新的个体;同时将“父代”中适应度高的个体进行复制,成为新一代个体,不断操作、迭代,以形成新的一组解(“子代”),计算个体适应度。如此反复,可求出整个种群的最优解。

遗传算法具有良好的全局搜索能力,可以快速求出全局最优解,但存在过早收敛和搜索效率低、局部搜索能力低的缺点,导致算法比较费时。目前,许多遗传算法在车辆调度问题中应用的研究都通过对编码、遗传算子的设计、基因构建和定义、适应度定义等方面来改进算法效能,如李军[1]等设计最大保留交叉来保证群体的多样性求解非满载车辆调度问题等;也有许多学者通过在遗传算法中引入其它算法来增加其局部搜索能力,如张涛[2]等用3-OPT算法结合遗传算法来加强算法的局部搜索能力,得到针对车辆调度优化问题的混合算法等,而随着模型变化,车辆调度优化问题的求解算法也会有所改变,如Giselher[3]等利用GA算法对装卸混合问题进行了研究。可见,遗传算法正从多方面影响着车辆调度问题。

2.2 模拟退火算法

模拟退火算法(Simulated Annealing,SA)由Kirkpatrick等人于1983年成功引入组合优化领域。模拟退火法是源于材料科学和物理领域的一种搜索过程。模拟退火算法的基本思想是:首先,任意选择一个初始状态,并设定初始温度和降温次数,并在邻域中产生另一个解,根据控制参数t选择接受和舍弃,经过大量操作后,求得给定t时优化问题的相对最优解;其次,通过降温函数,不断减小t的值直到0时的最后系统状态对应优化问题的全局最优解。前半部分是通过加热增加物体能量;后半部分是通过降温和冷却降低物体的能量。对应数学模式时,问题的解就是系统状态,而问题的目标函数就是物体的能量,因此求最优解的过程就是求能量最低态的过程。

模拟退火算法的优点是有很强的全局搜索能力,但是由于允许移动到较差的解,所以可能接受目标值不好的状态,从而使算法陷入局部最优,所以要求出最优解要花费较长时间。而模拟退火的有效性取决于邻域选择设计,如果邻域以一种促进移到更好解而移出局部极小解的方式设计,那么算法将会表现出其优越性。谢秉磊[4]等用模拟退火算法求解配送/收集旅行商问题;蔡延光[5]等用模拟退火算法求解多重运输调度问题等。由于模拟退火算法一个显著缺点就是收敛速度慢,因此在求解车辆优化调度问题时,多将模拟退火算法与其它智能算法结合,加快收敛速度。

2.3 禁忌搜索算法

禁忌搜索算法(Tabu Search,TS)由Glover在1986年提出。禁忌搜索算法是用一个禁忌表记录已经到达过的局部最优解,确保在下一次搜索过程中,不再选择这些点,从而跳出局部最优解。禁忌算法的基本思想是:首先,从一个初始可行解s开始,确定解的搜索邻域N(s),在这个邻域内选出最优解s′,则从s移到s′继续搜索;其次,设定禁忌表最大容量,将每次的移动根据先进先出准则放入禁忌表中,在每次迭代中,表中的移动是可能被禁止的,这都取决于一个渴望水平函数,这个函数用来评价移动的损益,如果损益是可以接受的,则移动不被禁止,反之,移动被禁止;最后,根据迭代停止准则,求出问题的最优解。

从上面的算法描述中可以看出,禁忌搜索算法的主要缺点是对初始解的依赖性很强,当遇到不好的初始解时,将会导致计算时间过长。而且禁忌表最大容量的设定对禁忌搜索算法来说也起着很重要的作用,因为如果容量过多,将会导致搜索被过分限制,造成时间浪费;而容量过少,会造成循环,不利于求解。由于禁忌搜索算法只能对一个解进行操作。钟石泉[6]等在求解多车场车辆调度问题时,以一组初始解的邻域作为搜索空间,突破点点操作,减少禁忌搜索算法对初始解好坏的依赖;并且采用局部、全局两种禁忌表来避免重复操作。但总体来说,禁忌算法比较容易与其它启发式算法相结合构建混合算法。结合之前介绍的两个算法,可以看出,遗传算法在每次迭代中都会生成很多不同的调度,而且会延续到下一次迭代,而在模拟退火法和禁忌搜索法中,只有一个调度从一次迭代延续到下一次迭代。

2.4 蚁群算法

蚁群算法(Ant Colony Algorithm,ACA)由意大利学者M.Dorigo及其导师Colorni于1991年提出并用于求解TSP问题,它是根据自然界中蚂蚁觅食行为而提出的一种优化算法。蚁群通过寻找信息素浓度最高的路径,从而求出最佳路径。蚁群算法的基本思想是:首先,初始化各蚂蚁,将m只蚂蚁放在n个顶点上,并设定初始参数,并将初始解置于当前解集中;其次,每只蚂蚁根据选择策略和转移概率选择顶点,并将该顶点置于当前解集中,则蚂蚁从初始点转移,不断操作,直到所有的点都已置于解集中,则求出各蚂蚁的适应度,记录当前最优解;通过更新信息素,不断迭代,直到结束条件满足,求出种群进化后的最优解,也就是问题的最优解。

蚁群算法的优点是其正反馈机制和分步式计算。但对于规模较大的问题,其搜索时间长且易收敛至局部最优解。目前,蚁群算法收敛性方面的理论成果则非常稀少。马良[7]等通过在蚁群算法的基础上嵌入2-OPT等算法加速其循环最优解的得出来求解带容量限制的多目标车辆路径问题;陈金[8]等结合sweep和saving算法确定客户归属的混合算法求解带时间窗的中转联盟运输调度问题。而蔡延光[9]等人也提出调整选择策略、信息素浓度与挥发速度的同向关系调节信息素更新方程的方法改进传统蚁群算法求解带软时间窗的联盟运输调度问题。许多学者在求解车辆优化调度问题时都对蚁群算法作了多种改进,这些改进都具有很强的意义。

2.5 微粒群算法

微粒群算法(Particles Swarm Optimization,PSO)由美国心理学家Kennedy[10]和电气工程师Eberhart于1995年提出。微粒群算法起源于鸟类在搜索食物过程中,个体之间可以进行信息的交流和共享,每个成员可以得益于所有其他成员的发现和飞行经历[11]。微粒群算法的基本思想是:首先,产生一组初始解,得到初始位置并初始化速度、个体最优解、全局最优解;然后,通过位置更新方程和速度更新方程产生一组新的解,并更新个体最优解和全局最优解;如此不断操作迭代,粒子渐渐向最优解靠近,直至到达循环结束条件,此时得到问题最优解。

微粒群算法有通用性强,具有记忆能力,保留个体和全局最优信息,协同搜索的优点。但微粒群算法局部搜索能力较差,通过多点同时搜索,使运算时间大大减少,但也造成了计算精度较差的特点,所以要设置迭代次数较多,此外算法对参数设置具有很强的依赖性。现在对微粒群算法的应用研究很多,朱露露[12]等采用量子算法与微粒群算法相结合的混合算法,通过采用一种二进制的编码方式求解了经典的车辆路径问题。因此在处理车辆优化调度问题时,也可以将其它算法的思想引入到微粒群算法中,从而克服其易陷入局部最优的缺点。

3 对未来研究方向的展望

车辆优化调度问题一直是配送运输领域关注的热点,诸多学者都对其进行了不少研究,也取得了不少成果。在对该问题的算法研究虽然种类很多,但实现起来都存在不少问题。根据学者们现有的研究发现,目前对算法的改进主要表现在以下几个方面:其一,通过混合算法的方式,结合各算法优点,弥补各算法缺点,形成一条可行的方案;其二,根据对自然界的不断探索以及结合交叉学科的方式,提出新的算法;其三,改进现有算法,就现有算法中各步骤中的细节进行调整。诸如此类的研究还在进行中,因此研究车辆优化调度问题是有潜力、有意义的。

摘要：配送车辆调度优化问题旨在解决配送中路径和车辆调度问题的一类组合优化问题,是近年来物流控制优化领域的研究热点。文章对运输调度问题进行了分类总结,给出总体模型的概括描述,分析遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法和微粒群算法的特点及其在求解配送车辆调度优化问题中的求解思路,并讨论了其求解现状,对未来研究方向进行展望,指出改进混合现有算法,开拓新算法将是更有效解决配送车辆调度问题的好方法。

物流配送的车辆调度排班问题分析 篇6

将目标货物从发货人送至收货人的过程被称为配送。由于配送最终的目标是收货人,即为消费者,因此,配送也是物流系统中的一个至关重要的步骤。配送不仅仅局限于配货和送货。满足客户的需求,配送需要在满足客户对货物种类数量的基础上,在保证按时送达客户的基础上选取更快,更节约成本的配送方案,实现利益最大化。

2 物流配送的流程

随着物流配送的发展,现代的物流配送水平的提高,货物流通性大大增强,配送环节取代存储环节成为物流中最重要的部分。而作为配送的核心配送车辆对货物的集货、配送和送货过程越来越被重视,如何选取最优配送路线,是对整个物流质量的考验,关系着物流整体的运输速度,服务成本和经济效益。随着电子商务的崛起,许多国外物流企业如UPS、Fed EX、德国邮政等公司已经从单纯的配送业转型成为以集货作业和配货作业作为主体的新物流模式。

3 车辆优化调度问题的现状

在我国境内,车辆调度问题的发展比国外晚发展近乎三十年,所以现在我国对于较为复杂的车辆调度路径问题研究还是相对落后。由于我国对这方面研究起步较晚,对于通用理论研究不够深入,再加上我国对于应用研究的问题提出虽多但在具体算法上的改进并没有创新,所以我国在车辆优化调度的问题上根本无法满足配送业和物流业的发展需求。随着物流业在市场上的地位日益重要,为了克服我国在车辆优化调度上局限性较强的弱点,我国逐渐开始对车辆优化调度问题进行深入的研究。

4 配送的算法

例如在现实生活中,会有配送中心的多台配送车辆为多家客户送货的情况,如果每个客户的位置和货物需求量一定,运输车的容量相同,每辆车运送货物后要返回配送中心,为防止超载,在考虑配货的同时更应注意每条配送路径上客户的需求量之和不能大于运输车的载量,更要满足每个客户需求。解决此类调度问题有很多方法,根据这些方法在算法上的本质研究可分为三大类,即精确算法、启发式算法、动态求解算法。

4.1 精确算法

精确算法又称最优化算法,是指求出最佳解的算法。其算法有很多,比如切割平面法,网络流算法等。

精确算法有一个弊端,就是其计算量随着需要解决的问题规模的增大而大幅度的增大。由于这个弊端,精确算法只能适合解决规模较小的问题。因为精确算法适应能力较差一般这种算法最适合解决一个特定的问题,所以在实际应用中这种算法不是很受提倡。

4.2 启发式算法

启发式算法完全不同于精确算法,它追求的是解决问题的满意性而不是最优性。它是一种用直观、经验构造出来的算法。到目前为止,启发式算法已经有好多种,最主要是以下两种算法。

构造启发式算法,其实质就是按照标准将不在同一条线路的所有点逐个的增加进来。在算法的每一步上,都要将当前的线路构形和另外的线路构形比较后,综合改进得到最后可行的构形。这类算法的的代表算法是:最邻近法、扫描法、节约法等。

智能化启发式算法就是在人工智能的启发式算法的基础上发展的。它的主要算法有:蚁群算法、神经网络算法等。

5 动态优化策略

动态车辆调度问题相对前两种比较其问题的规模较大解决起来相对比较困难些。并且这种算法的要求是在短时间内就要相应的实时信息。从求解策略上把动态求解算法分为重新优化策略和局域优化策略。

5.1 优化策略

重新优化策略就是当接收到一个新的实时信息时,要重新开始寻找始发到结束的最优车辆的行车路径。实质就是静态方法解决动态问题。研究运送大宗商品的车辆调度问题就是一个较为成功的运用重新优化策略的例子。还有在动态单车问题上,采用了乘子调整技术的静态算法。其算法过程是:当有新实时信息时,就采用动态重新优化法解决,可是这种算法最多能解决十种问题。

局域优化策略的实质是:提前拟定一些路径的模板,当收到实时信息时,就在提前拟定的模板里进行搜索,找个适合的路径进行使用。这种策略和重新优化策略相比较,路径可能是较差的,但是计算量是大大的减少了,从而节约了许多的时间。局域优化策略在实际的车辆调度上比较适用,所以受到重视和进一步的研究。

5.2 实际问题的解决

现代物流企业的核心任务就是合理优化配送资源。在终端物流企业配送的体系中,货物的配送是由总仓库运输到子库,子库到各大营销点。这个过程中的运用统筹学中的知识解决配送安排运输的问题,这个问题P可以这样描述:设子库的集合是A,配送车子的集合是B,A和B集合中的元素是一一对应的。现在有n项运输任务,其总集合记作N,将货物需求量的总集合记作G。将以上的零售点、子库道路、车辆、运输任务、货物运输这些量制作一个网络图。这个任务的要求是所有的参与配送车辆的任务中,需要的配送车辆数、运货的数量、运输路线等顺利完成后使其总的费用是最少的。

对于上述的终端物流配送的显著特点是面向对象是零售户,零售户的特点就是对货物的需求量很少。因为这个,所以这个问题就转变成了一个非满载的车辆调度问题。这个问题比较复杂,其复杂在每个子库就是一个MTSP,这个TSP的特点是可以有重复的路线。在这个问题上,一辆车的载量是有限的,而且每个零售点的需求又是固定的。从上述可以证明这个问题又是一个非确定性多项式NP,在求其解的过程中,计算量的大小变化是随着点n的增长而增长,并且还是呈指数倍增长的,这就给计算增加了许多困难。

通过对上述问题的分析,实属NP难题,由于实际应用中点的个数n会不断的增大,这就给计算最优解造成一定的困难。我们可以按照这样的思路进行分析求解,将问题P简化成四个问题,即子库分派、车辆分派、线路确定、迭代优化。通过对这四个问题的分析,针对每个问题,根据集合的划分,利用适合解决问题的算法进行求解,严格按照各个算法的实现步骤,最终达到解决总的NP问题的效果。

对于问题P来说,要想解决它就要求出各点之间的最短距离,不论采用的是什么算法,这时间复杂度大约是O(n3)[6]。在上面的算法中,在经过P1到P2过程中就减少变量N的数值,最后使得终端物流配送N的值建好为70左右。因为P3的时间复杂度为O(n4),相比较后可以看出这个算法是可行的。在算法中只要确定了P2,还安排最优的P3的线路,这样整体的优化程度已经完成。NP问题中的车辆分派算法有效的在一开始就得到了较优解。因为在P1到P3问题的解决上得到的都是较优解,所以对于P4问题可以根据具体情况选择执不执行。通过对上述问题的模拟试验,大量的配送计算问题可以在仅仅15分钟内完成。

6 结语

随着物流业和配送业在市场上的发展需求逐步扩大,车辆优化调度问题就日益重要。国外在车辆优化调度问题上发展较快,已经在生产和生活方面广泛应用并且得到了很好的经济效益。可是我国在车辆优化调度问题上的发展起步较晚,发展速度相对较慢,不能满足我国经济发展的需求。所以为了使我国国民经济发展迅速、人们生活质量的提高,就要在物流配送业上大力研究发展车辆优化调度问题。其主要研究方向就是:根据车辆优化调度的分类标准,以及各类问题上的特点应该按照何种算法进行优化;在基本算法的基础上针对特点问题如何改进;在不同地理环境和运输特点的基础上结合车辆优化调度问题上的优化算法,设计出更加适用的优良算法。按照这个方向研究发展,车辆优化调度的问题在现实生活中的意义会更加重要。

参考文献

[1]郎茂祥.配送车辆优化调度模型与算法[M].北京:电子工业出版社,2009,6.

[2]张之富,余静.基于改进遗传算法的车辆优化调度研究[J].中国水运,2009,(4),113-115.

城市配送车辆 篇7

在越库配送中,为了实现准时制配送,降低库存,必须对车辆调度进行深入研究,国内外许多学者均致力于此方面的研究。文献[1]针对美国邮电局邮件优先投递传送系统的卡车运输网络进行了设计,利用整数规划松弛法解决大规模系统的物流配送网络,为解决类似模型提供了依据。陈火根[2]等人针对在已知配送中心位置、客户点位置及道路情况下,对m辆车n个客户点,确定车辆分配(每辆车负责的客户点)及每辆车的行车路线,所采用的方法为遗传算法。林方明[3]等人研究了运输网络优化问题在物流配送决策中的作用,并探讨了物流企业应如何设计运输网络,提出运输网络优化的方法,以降低供应链成本,提高客户响应度。本文作者[4]针对越库作业调度问题提出两阶段越库作业调度模型,并给出了求解该类问题的动态规划算法。本文则是基于遗传算法来设计与上述问题不同的越库配送中心车辆运输网络。

1 问题描述

本文所研究的问题为越库配送中心车辆运输网络的设计,在配送中心内部某些客户需要的货物较多且可以直接从供货商或上级分销商处运走,而无需经过配送中心的整合运输,因此主要考虑车辆是否直接从出发点或通过配送中心将货物运输至目的地,以及每条运输线路上车辆的分配。例如,在连锁超市行业中,门店的货物主要通过配送中心集中进货与供货,在降低门店库存的同时,必须保证门店货物供应的及时性,以提高顾客满意度。因此,必须对配送中心的配货车辆及线路进行设计,从而保证货物及时、准确的到达指定地点,降低运输成本。为了更好地研究配送中心车辆调度问题,我们通过建立模型实现配送中心的车辆调度,确定各条线路上需要的车辆数(起点到终点、起点到配送中心)以及车辆线路安排。

图1描述了该模型的运输网络,由图可知:起点到终点的运输方式,可以是直接运输,也可通过配送中心整合后运输到终点。评价运输方式好坏的指标是运输成本。其数学模型如下:

式中:变量O,R,D为卡车数量,x表示流量。i为所有车辆起点的集合;j为终点集合;K为越库配送中心;xkij为经过配送中心由起点i到终点j的流量;xij为直接从起点i到终点j的流量;Rij为线路ij上由起点i开往终点j的车辆数;Oik为线路ik上起点到配送中心K的车辆数;Dkj为线路kj上配送中心到终点的车辆数;cij为一辆卡车从i到j的费用;C为卡车的承载能力;Sij为起点i到终点j的需求量,且xij≥0,xkij≥0,Rij=0,1,若车辆经由起点i开往终点j,则Rij=1,否则Rij=0;Oik,Dkj为正整数;同时假设所有满载的卡车不经过配送中心而直接从起点i开往目的地j,即Sij≤C。在上述模型中,目标函数为最小化运输成本。约束条件(1)保证所有的目的地都通过直接运输或经过配送中心运输来满足需求。约束条件(2)、(3)保证经过配送中心运输的卡车都尽可能装满。约束条件(4)保证直接运输的卡车都尽可能装满。(注:由于满载卡车直接从起点i直接运到终点j,因此其载货量不超过Sij)。

2 遗传算法的建立与求解

求解车辆调度问题的方法很多,常用的有旅行商法、动态规划法、分支定界法、方案评价法等。遗传算法的出现为求解物流配送问题及车辆优化问题提供了新的工具。许多学者利用遗传算法求解该类问题[5,6,7]。基于所研究问题的复杂性及问题的特点,本文亦采用遗传算法进行求解,下面针对算法具体参数进行研究与分析。

由于此模型中约束条件较多,在解决消除约束条件是需采用修改可行解的方法,其解空间为这种方法使个体的编码由两部分组成,前面部分的Rij的取值为,*01+,而后面的xkij需要根据Rij的值来修改,因此选用二进制编码作为个体的编码方式。

2.1 适应度函数。

针对本文研究的模型,不能直接简单地将个体解码后直接代入目标函数中计算目标函数值,从而衡量个体的适应度。因为对于具有实际意义的模型,各个变量均有严格的约束条件,而个体在进化过程中,无法保证一直满足约束。因此,即使得到的目标函数值很小,但只要不满足约束条件,该个体依然属于“劣质”个体。为此,需要对约束条件进行处理,使对个体好坏的评价更加符合实际情况。

2.2 采用修改可行解的方法消除约束条件。

很多研究表明:惩罚函数法消除模型约束条件在运输问题中并不是非常有效,其主要原因是在约束条件非常多,且约束严格的条件下,个体通过交叉变异很难找到可行解,因此很难找到一种合理的惩罚函数,使选择算子尽量地选择可行解,同时不破坏群体的多样性。DNA技术发展提示我们:依据医学技术,对遗传因子进行人为修改,使它具有我们想要的特征[8]。基于这种启发,设想对于本文所研究物流模型的遗传算法,作如下变换:在由个体基因型解码后,计算个体适应度前,增加处理个体表现型的过程,使其满足模型的约束条件。通过采用修改可行解的方法消除上述困难,且改进后的算法在较短时间内即可获得满意解。同时,修改可行解的方法也在很大限度上减少了解空间的编码长度。其具体做法如下:模型初始的解空间为

对于一个个体的代码,先通过解码得到解的形式,然后根据Rij的值得到xij的值,再根据xij的值修改相应的xkij,最后通过修改后的xkij值,计算得到Oik、Dkj。然后根据Rij和Oik、Dkj的值计算目标函数的值,作为适应度函数的值。通过修改可行解的方法,将个体的解空间精简到对于一个配送中心的配送系统模型,其代码长度缩短了。配送中心数量在一个以上的模型中,代码长度缩短的程度也相当可观。通过数值实验表明,代码长度直接影响算法的计算时间,通过修改可行解的方法大大减少了算法计算的时间。同时由于规模较大时,代码长度可能会超出编程语言的限制,因此,只能通过减小群体大小的方法来满足该限制。修改可行解的方法则最大限度地保证了可以取得足够的群体大小,使遗传算法有效的找到模型的满意解。

2.3 初始群体的生成。

针对该模型特点,提出了初始群体的生成方法(把它命名为确定式随机生成):假设群体大小为M,个体顺序按照0,1,…,n,…,M的顺序,分别在!0+i*j*n/4M,i*j*3/4+i*j*n/M"范围内的代码设置尽可能出现1,其它前i*j的代码为0。但这样,无疑在!i*j/4,i*j*3/4"范围内1的出现的频次远大于其它位置,然后,随机将该值改成0。这样,每个位置的“0”和“1”出现的概率都一致,但不同的个体,“0”和“1”在不同的位置上,出现的概率不同。对于长度很大的代码,可以尽可能的增加个体差异性,增大交叉算子的效果。

2.4 遗传操作。

遗传操作包括三个基本遗传算子:选择、交叉和变异。基于所研究模型的特点,选择算子采用确定式采样选择:由于算法的适应度就是模型目标函数的值,虽然不同的配送方案目标函数的差异很大,但轮盘算法依然很难保证选择尽量多的个体。而确定式采样选择可保证选择尽量多的个体,同时改进了选择算子,以保证遗传群体的多样性。交叉算子选择多点交叉:由于个体编码长度非常长,因此可采用多点交叉,以保证编码充分的交叉,增加全局搜索的能力。同时,基于编码的特点:前i*j个代码为直接运输的决策变量,它们对模型的影响要远远大于后面的其他代码。而后面的代码可能由于前面代码的变化而做出相应的修改。因此变异算子也要做出相应的修改。

在遗传算法前期,为了增加算法的全局搜索能力,对前i*j个代码进行变异,而前i*j个代码每个代码表示一个基因表现型,所以变异算子步骤如下:(1)随机产生一个变异概率pr,决定一个群体中变异的个体数量。(pr*M为整数);(2)随机产生pr*M个0,#M$的整数,确定变异的个体;(3)对每个个体产生pm*i*j个%0,pm*i*j&的整数,确定每个个体的变异基因的个数和位置,并对其取反。

遗传算法后期,主要增加的是算法的局部搜索能力,所以变异的主要基因作为i*j个代码后面的代码,方法和上面的一致。

同时,在算法后期改变变异算子的变异方法。由于编码的特点,前面对Rij的变异更多地影响着全局搜索能力,而后面xkij的变异则增加了算法的局部搜索能力。更加符合算法的原理:先增大全局搜索能力,寻找比较满意的结果,然后通过局部搜索找到足够满意的解。

3 数值试验

为了验证算法的有效性,下面用实例来比较。实例如下:在某连锁零售超市企业,其配送中心负责7个门店的货物供应,同时,所需货物须向7个供应商订货。根据其某一时期的需求量和各线路的运输费用,通过算法获得车辆的最佳调度模型。每辆卡车的载货量为20,需求情况和运输路费情况如下所示:

对于整数规划问题可用Lindo软件,因此下面就用该软件求解此模型。同时将门店和供应商数量增加为8个和9个,进行比较。得到了如下结果:

采用遗传算法求解时算法参数如下:二进制编码、随机生成初始群体、确定式采样选择算子、群体大小为200、遗传代数500、交叉概率0.8、交叉点个数5、变异个体个数概率0.05,变异点概率0.03、遗传90%代后改变变异算子。通过算法计算得到了如下的结果:(同样通过10次计算,得到10组满意解的钧值、方差,以此与Lindo计算情况作对比)

算法得到的满意解与最优解的误差分别为0.78%、0.22%、-2.6%。其中-2.6%,其原因为Lindo所用分支定界法无法求得最优值,程序内存溢出前各分支的最小值。由结果分析可知:对于小规模越库配送系统,此算法可以在很短的时间内得到满意的结果。而当供需商达到各9个时,算法在30秒内计算得到的满意解,比Lindo计算的满意解更接近最优值,且计算时间缩短了近十倍。测试结果充分表明该算法的有效性和快速性。

对于大规模配送系统,可行解比小规模配送系统更具有多样化。可能无法如同小规模配送系统案例那样,在算法遗传500代就得到足够满意的解。对于超过50个供应商、50个门店,以及3个越库配送中心的案例,也可以在30分种内完成500代的算法计算。由遗传算法的原理可知,遗传代数和计算时间之间为线性关系,可以通过在可行的时间内,通过增大遗传代数的方法得到足够满意的解。

4结束语

本文研究了越库配送网络系统中车辆调度问题,在给出问题的数学描述后,提出了求解该问题的遗传算法。算法特点为:(1)采用修改可行解的方法消除约束条件;(2)在算法后期改变变异算子的变异方法。

另外,本文的研究主要针对配送中心网络,通过研究运输车辆调度问题来减少网络中的运输费用。通过数值实验,还可以看到配送系统合理设计取得的经济效益。对于一个较小规模的7个供应商、7个门店、1个配送中心的案例,如果不经过配送中心的配送,而是直接运输,得到的运输费用为654。而通过配送中心配送的最佳运输方式的费用为382。这种规模经济效应还会随着配送网络系统规模的增大而增大。由此可知物流配送技术的前景,同时说明了研究物流配送技术的重大意义。

摘要：针对物流配送中心车辆调度问题,采用混合整数规划方法进行建模。对实际问题进行研究分析后,基于所研究问题的特点,提出基于遗传算法的求解方法。通过数值实验对算法不同参数组合进行分析、比较,获得最佳参数组合,建立了有效的求解该问题的遗传算法。并通过对实际问题的数值仿真试验,验证了算法的有效性。

关键词：配送中心,车辆调度,优化,遗传算法

参考文献

[1]Harvey Donaldson,Ellis L.Johnson,H.Donald Ratliff,Mei Zhang,Schedule-Driven Cross-Docking Networks[R].Technical report.The Logistics Institute,Georgia Institute of Technology,Atlanta,GA.2003.

[2]陈火根,丁红钢,程耀东.物流配送中心车辆调度模型与遗传算法设计[J].浙江大学学报:工学版,2003(5):512-516.

[3]林方明,马建军,庞渊.物流配送决策中的运输网络优化问题研究[J].山西建筑,2004(8):84-85.

[4]马东彦,陈峰.以总加权完工时间和为目标的约库作业调度问题及其动态规划算法研究[J].上海交通大学学报:自然科学版,2007(5):852-857.

[5]孙福春,宁槟.遗传算法在车辆调度问题中的应用[J].交通与计算机,2005(2):21-23.

[6]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000(3):35-40.

[7]王惠,陈燕.基于遗传算法的多目标的有时间窗的车辆调度[J].计算机应用,2004(9):144-147.

[8]陈曦,林涛,唐贤瑛.遗传算法的参数设计与性能研究[J].计算机工程与设计,2004,25(8):1309-1310,1319.

[9]姚城.物流配送中心规划与运作管理[M].广东:广东经济出版社,2004.