13
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.7.6 设计算法的算法流程
步骤1：初始化；给定群体规模maxpop，当前进化代数k=0，改进的节约 法和随机方法产生初始群体pop(k)，计算初始群体的适应度函数值； 步骤2：选择；若满足终止规则，转步骤5，否则，根据运用最佳保留策略) 和随机联赛选择机制混合法从初始群体中选择maxpop个染色体形成种群； 步骤3：交叉；由交叉概率对种群中的染色体进行启发式交叉； 步骤4：变异；由变异概率对种群中的染色体进行倒立变异；转步骤2； 步骤5：终止算法，输出计算结果。
6
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.1.1 配送
配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包含 了商流活动和物流活动，也包含了物流中若干功能要素的一种形式;它是指在 经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、 组配等作业，并按时送达指定地点的物流活动。 从经济学资源配置的角度，配送是以现代送货形式实现资源最终配置的经济 活动。 第一，配送是资源配置的一部分，因而是经济体制的一种形式。 第二，配送的资源配置作用是“最终配置”，因而是接近顾客的配置。 第三，配送的主要经济活动是送货。 第四，配送在社会再生产过程中的位置是处于接近用户的那一段流通领域， 是一种重要的方式，有其战略价值。
3
§11.2 分送式配送运输
11.2.1节约法的基本规定
该方法确定配送线路的出发点是，根据配送方的运输能力及其到客户之间的 距离和各客户之间的相对距离来制订使配送车辆总的周转量达到或接近最小 的配送方案。
为便于介绍，假设: (1) 配送的是同一种或相类似的货物； (2) 各用户的位置及其需求量已知; (3) 配送方有足够的运输能力 ; (4) 状态参数为tij。
4
§11.2 分送式配送运输
11.2.2节约法的基本思想
根据节约法的基本思想，如果一个配送中心分别向N个客户配送货物，载汽 车载重能力允许的前提下，每量汽车的配送线路上经过的客户个数越多，里 程节约量越大，配送线路越合理。
5
§11.3 配送式运输
配送式运输是指由多个供应点向多个客户的送货运输。它的宗旨是将货物从 多个供应点分别送到多个客户手中，既满足客户对货物的配送需要，有满足 各供货点存出货要求，并最终做到费用最省。
9
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.4 变量及参数定义 11.4.5 数学模型 11.4.6 模型算法复杂度分析
由组合优化问题的定义可知，每一个组合优化问题都可以通过枚举的方法求 得最优解。但是，枚举是以时间为代价的，有时枚举的时间是可以接受的， 有时则是不能接受的，那么对于复杂的组合优化问题有必要设计出好的求解 算法。
10
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.7 算法设计
11.4.7.1 染色体编码与译码
VRPSPD的解对应访Байду номын сангаас所有客户的若干路径的组合，由于遗传算法一般不 能直接处理解空间的解数据，必须通过编码将问题的解表示成遗传空间的基 因型串结构数据。
11.4.7.2 初始群体的生成
初始群体中个体的组成结构对进化结果有着很大的影响，一般说来，初始群 体的个体越优良，进化出最优解的可能性越大，但同时还必须注意保持个体 的多样性，否则可能会导致进化陷入局部极值点。初始群体的生成方式一般 是基于随机生成的方式或启发式生成方式
Hitchcock运输问题的一个重要特征是，在最优点上，最多只有I+J-1个 变量有非零值，其他变量均为零。 第一步 设置一个只有在I+J-1条弧上有流量的初始可行解。 第二步 检查能否通过增用某条空弧来改进解。若否，停止运算；若能，继 续。 第三步 决定能安排到空弧上的流量（不违背约束）。 第四步 调整其它弧上的流量，更新网络且转第二步。
7
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.2 集货
集货和配送的主体活动都包括运输，只是其在方向上相反。这里集货是指运 输终点为企业的物资流，包括供应链上的采购物流和逆向物流等。
采购物流是指将采购的原材料、零部件由供应商处运入厂内，采购是企业物 流的起始点，采购物流的科学管理对于企业生产、运作的科学系统管理有着 极其重要的作用。 逆向物流是指物资从产品消费点(包括最终用户和供应链上的客户)到产品来 源点的物理性流动。
11 运输路线选择问题
目录
1
最短路问题
2
分送式配送运输
3
配送式运输
4
具有同时配送和收集需求的车辆路径问题
2
§11.1 最短路问题
运输路线选择问题，最简单和直观的方法是最短路线法。 目前解决最短路线问题的方法有很多，如Dijksta算法、动态法、矩阵圈乘 算法。现以矩阵圈乘算法为例，介绍如何解决物流网络中的最短路线问题。
遗传算法的算子包括，选择算子、交叉算子、变异算子，由于设计的过程中 采用的是整数编码，各种算子的设计如下。 （1) 选择算子 （2）交叉算子 （3）变异算子
12
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.7.5 终止规则
终止规则就是确定什么时候终止算法，通常使用的有以下几种方法: ① 事先确定进化代数。 ② 给定问题的一个下界。 ③ 当算法再进化已无法改进解。 ④ 多种停止规则的组合。
8
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.3 问题概述及基本假设
VRPSPD可以描述为:用多台配送车辆将客户需要的货物从站点送到各个客 户，并将各个客户供应的货物从客户处收集回到中心站点，每个客户的位置 一定，客户处需要配送和收集的货物量一定且事先已知，每台配送车辆的载 重量一定，求车辆路线的合理安排，使目标函数得到优化。 (1)只有一个中心站点； (2)站点与客户（需求点）的位置坐标已知； (3)客户(需求点)的需求量和供应量己知； (4)车辆在配送过程中的载重量不得超过其最大载重量； (5)必须满足每个客户的配送和集货需求； (6)客户同时收、送货物； (7)车辆为同种车型，容量己知； (8)每个客户必须且只能访问一次；
11
§11.4 具有同时配送和收集需求的车辆路径问题
11.4.7.3 适应度函数的设定
适应度函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力， 是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应度加以 控制。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。
11.4.7.4 遗传操作的设计