|
第4章 遗传算法求解有时间窗非满载VSP 由于现在各任务需求点，如零售商店、连锁店等都尽可能的销售畅销商品，库存数量最好不要太多，且不能缺货，因此现在的物流配送一般是小范围、近距离、多品种、小批量、多批次、为多用户服务的经济活动，这时每个任务点的货物量小于车辆容量，用一辆车执行单一任务，属于非满载运行情况，在一辆车上同时装载有不同任务点的货物，所以物流配送车辆优化调度大部分是非满载车辆优化调度问题。 内容来自论文无忧网 www.paper51.com 时间窗约束下的物流配送运输在实际中是存在的，如某些特定的用户在断货时提出的紧急配送到货的时间要求、为饭店配送鲜活水产品、为有固定时刻表的火车、飞机等转运点送货以及超市配送用户要求送货不能太早于开门营业时间、也不能太晚于销售缺货时间等。 copyright paper51.com 有时间窗约束的车辆优化调度问题归结为车辆优化调度问题中的单车场、单车型、非满载、多约束（含时间窗约束）、多目标、车辆封闭的对点服务问题。该问题属于组合优化领域的NP难题［１１］，本小组尝试使用遗传算法求得该类问题的最优解或近似最优解。根据小组成员的分工，本文就适应度函数的选定和变异算子进行主要阐述。 内容来自论文无忧网 www.paper51.com
4.1 问题描述 内容来自论文无忧网 www.paper51.com 一般车辆优化调度问题可描述为：一个物流配送中心使用载重量相同的多辆汽车完成多个货物需求点的配送任务。每个需求点(供货点)的需求量(供货量)已知，且都小于配送车辆的载重量；配送中心和各需求点中任意两点间的运距已知或可以推算出来；一个需求点的任务只能由一辆车一次运送完成；每个配送车辆从配送中心出发，完成运送任务后返回配送中心。求满足货运需求和车辆载重量的费用最小的车辆行使线路。在日常生活中和生产实际中，许多类似的问题都可以归结为这类问题。如一个中心货场需向几个顾客有运送货物，每个顾客对货物有一定的要求，运送货物的车辆在货场装满货后发出，把货送到各顾客处，完成任务后，返回货场，如何确定满足用户需求的费用最小的车辆行使路线，即送货车辆优化调度。又如，若干厂家生产一些产品，需要运到配送中心，车辆从配送中心出发，到各厂家去装货，装满货后返回配送中心，在满足厂家发货要求的情况下，按什么线路行驶，可使总费用最小，即集货车辆优化调度。 paper51.com 有时间窗的VSP则是在一般车辆优化调度问题的基础上要求每项任务i在时间范围内完成，并可根据时间约束的严格与否，分为软时间窗和硬时间窗的VSP。由于有时间窗的VSP是典型的NP难题，会随着节点的增加出现组合爆炸的现象［５］。 内容来自论文无忧网 www.paper51.com 4.2 数学模型 http://www.paper51.com
4.2.1 一般VSP模型 paper51.com
物流配送中心拥有足够的载重量为q的车辆，现有n个需求点任务需要货物运输，以表示，已知第i个需求点的需要的货物量为，且。 http://www.paper51.com 一般来讲，当问题的约束越多，组织线路就越难，一辆车所完成的满足所有约束的任务就越少，这时，一辆车实际所能容纳的任务量要小，而所用的车辆数可能要多。为了使线路安排具有一定的弹性，可预先估计一个完成任务所需要的车辆数m： paper51.com (4-1) 内容来自www.paper51.com
其中，[ ]表示不大于括号内数字的最大整数，是对装车或卸车的复杂性程度及约束多少的估计，一般来讲，装(卸)车越复杂，约束越多，应越小，表示一辆车所能承载的货物量越小。本算法采用人机对话来调整的大小。 内容来自论文无忧网 www.paper51.com 为构造数学模型方便，将物流配送中心编号为0，需求点编号为，则物流配送中心及需求点均以点来表示，完成配送任务共需要车辆数目为，每辆车的载重量为，每个需求点的需求量为，配送中心及各需求点中任意两点间的距离为，第k辆车的行车路径称为第k条子路径，其中经过的需求点数目为，表示第k条子路径中包含的个需求点组成的集合，其中的元素代表第k条子路径中顺序为i的需求点；均表示配送中心，且有。得到车辆优化调度数学模型如下： 内容来自www.paper51.com (4-2) http://www.paper51.com
， (4-3) 内容来自论文无忧网 www.paper51.com (4-4) http://www.paper51.com
(4-5) 内容来自论文无忧网 www.paper51.com
；； (4-6) http://www.paper51.com 4.2.2 有时间窗VSP模型 内容来自论文无忧网 www.paper51.com
设完成任务i需要的时间(装货或卸货)表示为，又设任务i的开始时间需在一定的时间范围内，其中为任务i的允许最早开始时间，为任务 i的允许最迟开始时间。如果车辆到达i的时间早于，则车辆需在i处等待，如果车辆到达时间晚于，则任务i要延迟执行。求满足货运要求的费用最少的车辆行使线路。此问题称之为有时间窗的车辆优化调度问题。 http://www.paper51.com 以表示车辆到达点i的时间，一般应有以下关系式： 内容来自www.paper51.com (4-7) 内容来自www.paper51.com 硬时间窗VSP指每项任务必须在要求的时间范围内完成，即必须满足式(4-7)。若超出这个时间范围，则得到的解为不可行解［２］［４］。 内容来自www.paper51.com 软时间窗VSP指如果每项任务不能在要求的时间范围内完成，则给予一定的惩罚。惩罚成本函数的设定一般以配送中心与顾客在商议之后所签定的合同为主，但因实际上所签定合同是为维护买卖双方共同的利益，故考虑的因素相当多。若车辆在之前到达点i，则车辆在此等待，发生了机会成本损失。若车辆在之后到达点i，则服务被延迟，须支付一定的罚金。 http://www.paper51.com 4.3 算法设计 paper51.com 4.3.1 算法流程图 内容来自论文无忧网 www.paper51.com
算法流程图如图4-1示。 copyright paper51.com 4.3.2 染色体结构 http://www.paper51.com 为提高效率，对VSP采用自然数编码方式，即序数编码。 http://www.paper51.com 单车场车辆优化调度问题的一条可行线路可编成长度为的染色体，其中用自然数表示，代表编号为的需求点。这样的染色体结构可通俗地理解为第一辆车从配送中心0出发，经过需求点后，回到配送中心0，形成子路径1；第二辆车也从配送中心0出发，经过以前未访问的需求点后，返回配送中心0，形成子路径2；依次类推，直到所有的n个需求点全部被遍历，形成子路径m。如染色体021304605870表示的行车线路为： copyright paper51.com 子路径1: 配送中心0 →需求点2 →需求点1→需求点3→配送中心0 http://www.paper51.com 子路径2: 配送中心0 →需求点4 →需求点6→配送中心0 内容来自www.paper51.com 子路径3: 配送中心0 →需求点5→需求点8→需求点7→配送中心0 内容来自论文无忧网 www.paper51.com
内容来自论文无忧网 www.paper51.com
图4-1 遗传算法解决VSPTW算法流程图 paper51.com
这种染色体结构子路径内部是有序的，若子路径1中点1， 3相互交换位置，会使目标函数值改变；而子路径之间是无序的，若子路径1和2相互交换位置，却不会改变目标函数的值；若子路径倒转，如0460倒转为0640，也不会改变目标函数的值。 内容来自论文无忧网 www.paper51.com 4.3.3 约束处理 paper51.com 对于VSP这类约束较复杂的优化问题，用遗传算法求解时，需要对约束进行处理。一般有下面几种方法： paper51.com 1、问题的约束在染色体中表现出来，设计专门的遗传算子，使染色体所表示的解在遗传算法的求解过程中始终保持为可行解。 http://www.paper51.com 2、在编码的过程中不考虑约束，而在遗传算法的计算过程中检测得到的染色体相应的解是否可行，若可行，则放入下一代群体中，否则将其舍弃。 内容来自论文无忧网 www.paper51.com 3、采用惩罚的方法来处理约束。如果一个染色体对应的解违反了某个约束，试其违反程度给予一定惩罚，使其具有较小的适应度。这样，一些不可行解也有可能进入群体，以保证群体中染色体的数目，使遗传算法得以继续运行。若干代后，不可行解在群体中所占的比例应越来越小，可行解逐渐占据主导地位，并逐渐趋于最优解［５］［６］。 内容来自www.paper51.com 1、 载重量的约束处理 http://www.paper51.com 上述第一种方法是直接的处理约束的方法，但适用领域有限，而且设计专门的染色体和遗传算子较为困难，能否采用这一方法与问题的特征关系很大；第二种方法只适用于约束简单、可行解易于得到的优化问题，使用价值不高。在此采用罚函数的方法处理约束。 paper51.com 对于一般VSP，使用如下变换将承载量约束式变为目标函数式的一部分： http://www.paper51.com (4-8) http://www.paper51.com 其中 表示若解违反载重量约束处以的惩罚值。为第k辆车的超载量；maxpath是所有两点间运距中最大的运距；M为超载时施以的惩罚系数，即目标函数所加的最大的运距的倍数。 paper51.com 2、时间窗的约束处理 copyright paper51.com 本文采用软时间窗约束处理，以d表示车辆在任务点处等待损失的单位时间机会成本，e表示车辆在要求时间之后到达单位时间所处以的罚值。 copyright paper51.com 若车辆在之前到达需求点j则产生成本；若车辆在之后到达需求点j则处以罚款。用罚函数法处理时间窗约束，得到软时间窗VSP的目标函数： paper51.com (4-9) 内容来自论文无忧网 www.paper51.com |