当前位置：网学 > 设计下载 > VC与C++类别 > 正文

基于VC研究物流配送车辆优化调度问题

来源：http://myeducs.cn 联系QQ：

作者：用户投稿来源：网络发布时间： 13/05/14

鉴于大家对VC与C++类别十分关注，我们编辑小组在此为大家搜集整理了“基于VC研究物流配送车辆优化调度问题”一文，供大家参考学习

客服咨询，网学网竭诚为您服务，本站永久域名：myeducs.cn

4.3 算法设计

4.3.1 算法流程图

算法流程图如图4-1示。

4.3.2 染色体结构

为提高效率，对VSP采用自然数编码方式，即序数编码。

单车场车辆优化调度问题的一条可行线路可编成长度为的染色体，其中用自然数表示，代表编号为的需求点。这样的染色体结构可通俗地理解为第一辆车从配送中心0出发，经过需求点后，回到配送中心0，形成子路径1；第二辆车也从配送中心0出发，经过以前未访问的需求点后，返回配送中心0，形成子路径2；依次类推，直到所有的n个需求点全部被遍历，形成子路径m。如染色体021304605870表示的行车线路为：

子路径1: 配送中心0 →需求点2 →需求点1→需求点3→配送中心0

子路径2: 配送中心0 →需求点4 →需求点6→配送中心0

子路径3: 配送中心0 →需求点5→需求点8→需求点7→配送中心0

这种染色体结构子路径内部是有序的，若子路径1中点1， 3相互交换位置，会使目标函数值改变；而子路径之间是无序的，若子路径1和2相互交换位置，却不会改变目标函数的值；若子路径倒转，如0460倒转为0640，也不会改变目标函数的值。

4.3.3 约束处理

对于VSP这类约束较复杂的优化问题，用遗传算法求解时，需要对约束进行处理。一般有下面几种方法：

1、问题的约束在染色体中表现出来，设计专门的遗传算子，使染色体所表示的解在遗传算法的求解过程中始终保持为可行解。

2、在编码的过程中不考虑约束，而在遗传算法的计算过程中检测得到的染色体相应的解是否可行，若可行，则放入下一代群体中，否则将其舍弃。

3、采用惩罚的方法来处理约束。如果一个染色体对应的解违反了某个约束，试其违反程度给予一定惩罚，使其具有较小的适应度。这样，一些不可行解也有可能进入群体，以保证群体中染色体的数目，使遗传算法得以继续运行。若干代后，不可行解在群体中所占的比例应越来越小，可行解逐渐占据主导地位，并逐渐趋于最优解^{［５］［６］}。

1、 载重量的约束处理

上述第一种方法是直接的处理约束的方法，但适用领域有限，而且设计专门的染色体和遗传算子较为困难，能否采用这一方法与问题的特征关系很大；第二种方法只适用于约束简单、可行解易于得到的优化问题，使用价值不高。在此采用罚函数的方法处理约束。

对于一般VSP，使用如下变换将承载量约束式变为目标函数式的一部分：

(4-8)

其中表示若解违反载重量约束处以的惩罚值。为第k辆车的超载量；maxpath是所有两点间运距中最大的运距；M为超载时施以的惩罚系数，即目标函数所加的最大的运距的倍数。

2、时间窗的约束处理

本文采用软时间窗约束处理，以d表示车辆在任务点处等待损失的单位时间机会成本，e表示车辆在要求时间之后到达单位时间所处以的罚值。

若车辆在之前到达需求点j则产生成本；若车辆在之后到达需求点j则处以罚款。用罚函数法处理时间窗约束，得到软时间窗VSP的目标函数：