下载掌阅APP，畅读海量书库
立即打开
由爬山算法的实现步骤可以看出，用爬山算法求解组合优化问题时主要涉及解的表示、邻域选点方法、解的评价及算法终止准则等要素。下面针对无时限单向配送车辆优化调度问题的特点，分别对上述爬山算法的要素进行设计。下述各算法要素的设计同样适用于构造无时限单向配送车辆优化调度问题的禁忌搜索算法、模拟退火算法和遗传算法，也适用于构造有时限单向配送车辆优化调度问题及双向配送车辆优化调度问题的禁忌搜索算法和模拟退火算法。
用启发式算法求解配送车辆优化调度问题时，确定解的表示方法是一项非常关键的基础工作，因为它将直接决定算法实现的难易程度和算法性能的优劣。国内外学者研究用启发式算法求解配送车辆优化调度问题时用得最多的是客户与虚拟配送中心共同排列的解的表示方法。作者在现有研究成果的基础上，又提出了两种新的解的表示方法，分别为客户直接排列的表示方法及车辆和客户对应排列的表示方法。
第1章已经提到，通过增加虚拟配送中心，可将配送车辆优化调度问题这个多路旅行商问题转化为TSP，这种解的表示方法正是基于这种思想提出的。
用0表示配送中心，用1、2、…、L表示各客户。设在配送中心有K台配送车辆，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在一个解中反映出多条配送路径，可采用增加K-1个虚拟配送中心的方法，这K-1个虚拟配送中心分别用自然数L+1、L+2、…、L+K-1表示（这里之所以用L+1、L+2、…、L+K-1表示虚拟配送中心，而不直接用0表示，是为了便于用随机方法产生初始解，并保证当前解在经过有关算法操作后仍能保持解的有效性）。这样，1、2、…、L+K-1这L+K-1个互不重复的自然数的排列就构成一个解，并对应一种配送路径方案。例如，对于一个有7个客户，用3台配送车辆完成配送任务的无时限单向配送车辆优化调度问题，则可用1、2、…、9（8、9表示虚拟配送中心）这9个自然数的随机排列，表示配送路径方案。如解129638547对应的配送路径方案为：车辆1的配送路径0-1-2-9（0），车辆2的配送路径9（0）-6-3-8（0），车辆3的配送路径8（0）-5-4-7-0，即共有3条配送路径，需3台车辆配送；解573894216对应的配送路径方案为：车辆1的配送路径0-5-7-3-8（0），车辆2不参加配送，车辆3的配送路径9（0）-4-2-1-6-0，共有2条配送路径，需2台车辆配送。可见，用这种解的表示方法能够产生配送路径数小于车辆总台数的配送路径方案。
这种表示方法是直接产生L个1～L间的互不重复的自然数的排列，该客户排列就构成一个解，并对应一种配送路径方案。按照无时限单向配送车辆优化调度问题的约束条件，可依次将解的元素（客户）划入各台车辆的配送路径中。例如，对于一个用3台车辆向9个客户送货的配送车辆优化调度问题，设某解中的客户排列为412876935，可用如下方法得到其对应的配送路径方案：首先将客户4（解中的第1个客户）作为第1台配送车辆服务的第1个客户，然后判断能否满足问题的约束条件，即客户4的需求量是否超过第1台车辆的最大载重量，且路径0-4-0的总长度是否超过第1台车辆一次配送的最大行驶距离，设能够满足，这时可将客户1（解中的第2个客户）作为第1台配送车辆服务的第2个客户，然后判断能否满足问题的约束条件，即客户4和1的需求量之和是否超过第1台配送车辆的最大载重量，且路径0-4-1-0的总长度是否超过第1台车辆一次配送的最大行驶距离，设仍能满足，这时可将客户2（解中的第3个客户）作为第1台配送车辆服务的第3个客户，然后判断能否满足问题的约束条件，设仍能满足，这时可将客户8作为第1台配送车辆服务的第4个客户，设此时不能满足问题的约束条件，这说明客户8不能由第1台配送车辆服务，由此可得第1台车辆的配送路径为0-4-1-2-0；然后，将客户8作为第2台配送车辆服务的第1个客户，若能满足问题的约束条件，则可将客户7作为第2台配送车辆服务的第2个客户，若仍能满足问题的约束条件，则可将客户6作为第2台配送车辆服务的第3个客户，若仍能满足问题的约束条件，则可将客户9作为第2台配送车辆服务的第4个客户，若此时不能满足问题的约束条件，则说明客户9不能由第2台配送车辆服务，由此可得第2台车辆的配送路径为0-8-7-6-0；仍按上述方法可将解中的其他客户也依次加入到其他车辆的配送路径中。采用这种表示方法，也可以得到配送路径数小于车辆总台数的配送路径方案。若某个解中的排在最后的若干个客户不能纳入到车辆的配送路径中，则说明该解为一个不可行解。与前述客户与虚拟配送中心共同排列的表示方法相比，这种解的表示方法占用的计算机存储量较少，表示也较为直观，也容易产生可行解。
如前所述，求解配送车辆优化调度问题主要是要确定配送路径的条数及每条配送路径上的客户数量和客户服务顺序。基于这种考虑，现提出一种车辆和客户对应排列的解的表示方法。其基本思路是：用L个1～K间的任意自然数（可以重复）的排列表示车辆排列，用L个1～L间的互不重复的自然数的排列表示客户排列，两者相对应，可构成一个解，并对应一个配送路径方案。例如，对于一个用3台配送车辆向9个客户送货的配送车辆优化调度问题，设某解为（122131223）（456712398），即车辆排列为122131223，客户排列为456712398，两个排列相对应，则有：车辆1服务的客户为4、7和2，车辆2服务的客户为5、6、3和9，车辆3服务的客户为1和8。于是得该解对应的配送路径方案为：车辆1的配送路径为0-4-7-2-0，车辆2的配送路径为0-5-6-3-9-0，车辆3的配送路径为0-1-8-0。当车辆排列不能取到1～K间的所有自然数时，则这种解的表示方法也能产生配送路径条数小于车辆总台数的配送路径方案。同客户与虚拟配送中心共同排列的表示方法及客户直接排列的表示方法相比，这种表示方法占用的计算机存储量较大。在这种表示方法中，客户排列仅表示客户在各条配送路径中的先后顺序，相邻的两个客户并不一定在一条配送路径上，可见，这种表示方法不是很直观。
在用启发式算法求解配送车辆优化调度问题时，需要对解进行评价，以比较解的优劣，使算法在迭代过程中，不断搜索到质量更优的解，并最终得到问题的最优解或近似最优解。根据无时限单向配送车辆优化调度问题的数学模型，对于某个解要判定其优劣，首先要得到该解所对应的配送路径方案，然后要判断该配送路径方案是否满足问题的约束条件，同时计算该配送路径方案的目标函数值，在满足问题的约束条件的前提下，其目标函数值越优，则配送方案越优，解的质量越高。下面针对前述三种解的表示方法，分别讨论其解的评价方法。
根据配送车辆优化调度问题的特点，由该种表示方法生成的解所确定的配送路径方案，隐含能够满足每个客户都得到配送服务及每个客户仅由一台车辆配送的约束条件，但不能保证满足每条配送路径上各客户需求量之和不超过配送车辆的最大载重量及每条配送路径的长度不超过车辆一次配送的最大行驶距离的约束条件。为此，对某个解所对应的配送路径方案，要对各条配送路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条配送路径定为不可行路径，最后还要计算出该解对应的配送路径方案的目标函数值。对于某个解，设其对应的配送路径方案中的不可行路径数为M（M=0表示该解为一个可行解），该配送路径方案的目标函数值为Z，并设对每条不可行路径的惩罚权重为P w （该权重可根据目标函数的取值范围取一个相对较大的正数），则该解的评价值E可用公式（2.12）计算（E值越小，表示解的质量越高）。这种解的评价方法，体现了用罚函数法处理约束条件的思想。
用客户直接排列表示方法产生的解所确定的配送路径方案，能够满足每条配送路径上各客户需求量之和不超过配送车辆的最大载重量及每条配送路径的长度不超过车辆一次配送的最大行驶距离的约束条件，但不能保证所有的客户全部都能得到配送服务。对于某个解，若全部客户均能纳入到车辆的配送路径中，则取该配送路径方案的不可行路径数M=0，表示该解为一个可行解；若排在最后的若干个客户不能纳入到车辆的配送路径中，则取该配送路径方案的不可行路径条数M=1，表示该解为一个不可行解，设该解对应的配送路径方案的目标函数值为Z，将M和Z代入公式（2.12），同样可计算出该解的评价值E。
同采用客户与虚拟配送中心共同排列的解的表示方法一样，用车辆和客户对应排列表示方法产生的解所对应的配送路径方案，也隐含能够满足每个客户都得到配送服务及每个客户仅由一台车辆配送的约束条件，但不能保证满足每条路径上各客户需求量之和不超过配送车辆的最大载重量及每条配送路径的长度不超过车辆一次配送的最大行驶距离的约束条件。因此，可采用与基于客户与虚拟配送中心共同排列表示方法相同的解的评价方法，即首先确定该解对应的配送路径方案，然后根据配送车辆优化调度问题的约束条件，确定某个解所对应的配送路径方案的不可行路径条数M（若各条路径都可行，则取M=0），并计算出该配送路径方案的目标函数值Z，将M和Z代入公式（2.12），即可计算出该解的评价值E。
爬山算法、禁忌搜索算法和模拟退火算法都是基于邻域搜索技术的算法，因此，确定邻域选点方法是构造这些算法的一个重要步骤。由于邻域选点也可以看成是对原解实施的一种邻域操作，因此，在本书中也将邻域选点方法称为邻域操作策略。根据现有研究文献，在用爬山算法、禁忌搜索算法和模拟退火算法求解组合优化问题时，普遍采用换位法（特别是其中的两交换法）实施邻域操作。作者在现有研究成果的基础上，提出了两种新的邻域操作方法，分别为逆转法和插入法。
实施邻域操作后，要保证得到的原解的邻居仍为解空间中的一个点，即保持解的有效性。邻域选点方法也与解的表示方法有关，下面针对无时限单向配送车辆优化调度问题的三种解的表示方法，分别讨论其邻域选点方法。
采用客户直接排列的解的表示方法时，可以采用以下几种邻域选点方法。
（1）换位法。该方法是指随机选择解中的若干个元素，并交换其位置的邻域选点方法。最常用的是两交换法，现举例说明。设某解为S=123456789，随机产生的换位点为第4位和第7位，则实施两交换后可得原解的邻居S′=123756489。也可以采用随机选择解中的三个元素并交换位置的方法，称为三交换法，仍设原解为S=123456789，随机产生的换位点为第3位、第6位和第9位，则实施三交换后可得原解的多个邻居，如126459783、129453786等。
实际应用爬山算法时，每次邻域操作可以仅执行一次换位操作，也可以连续执行多次换位操作。
（2）逆转法。该方法是指在解中随机选择两点（两点间称为逆转区域），再将这两点内的元素按反序插入到原位置中。设某解为S=123456789，随机选定的逆转点为第4位和第6位，则经逆转后，可得原解的邻居S′=123654789。
实际应用爬山算法时，每次邻域操作可以仅执行一次逆转操作，也可以连续执行多次逆转操作。
（3）插入法。该方法是指从解中随机选择1个元素，并将该元素插入随机选定的插入点中间。设某解为S=123456789，若取插入元素为第5位，选取的插入点为第2位之后，则实施插入操作后得原解的邻居S′=125346789。
实际应用爬山算法时，每次邻域操作可以仅执行一次插入操作，也可以连续执行多次插入操作。
采用该种解的表示方法时，由于解中的元素仍为互不重复的自然数，这一点与客户直接排列表示方法相同，因此，上述基于客户直接排列表示方法的邻域选点方法在这里都同样适用，此处不再重述。
在这种解的表示方法中，解是由两部分组成的，一部分为车辆元素的排列，另一部分为客户元素的排列，相应地，邻域选点方法也有以下几种。
（1）仅对车辆元素的排列实施邻域操作。采用这种方法时，需要对车辆元素的排列实施邻域操作，而使客户元素排列保持不变。对车辆元素排列实施邻域操作时，上述几种基于客户直接排列表示方法的邻域操作方法，即换位法、逆转法和插入法都是适用的。例如，设某解为（321223211）（123456789），对车辆元素排列实施两交换邻域操作，换位点为第2位和第9位，则可得原解的一个邻居（311223212）（123456789）。除上述方法外，对车辆元素排列实施邻域操作时也可采用位点变化方法，即以一定的概率使解的某些元素的值发生变化，设原解仍为（321223211）（123456789），对车辆元素排列用位点变化方法实施邻域操作，若随机选定的变化位点为第3、5、7位，变化后的值分别为2、3、1，则可得原解的一个邻居（322233111）（123456789）。
（2）仅对客户元素排列实施邻域操作。这种方法是使解中的车辆元素排列保持不变，而仅对客户元素排列实施邻域操作。对客户元素排列实施邻域操作时，可以采用前述几种基于客户直接排列表示方法的邻域操作方法，即换位法、逆转法和插入法。设某解为（321223211）（123456789），对客户元素排列用两交换法实施邻域操作，换位点取为客户元素排列的第3位和第8位，则可得原解的一个邻居（321223211）（128456739）。
（3）对车辆元素排列和客户元素排列同时实施邻域操作。设某解为（321223211）（123456789），对其车辆元素排列用两交换法实施邻域操作，换位点为第2位和第8位；对其客户元素排列用逆转法实施邻域操作，逆转点为客户元素排列的第4位和第7位，则可得原解的一个邻居（311223221）（123765489）。
由于爬山算法是一种启发式算法，在迭代过程中，需要确定终止准则，使算法能在可接受的时间里得到问题的解。以下是几种直观、易于操作的终止准则。
（1）迭代一定的步数后终止的准则。该准则是指给定一个充分大的正数T，使总的迭代次数不超过T步。这种准则的优点是易于操作和可以控制计算时间，但当迭代步数较少时无法保证解的效果。
（2）频率控制准则。该准则是指在算法迭代过程中，当某一个解出现的频率超过一个给定的标准时，如果算法不做改进，只会造成频率的增加，说明此时的迭代对解的改进已无作用，因此，可以终止计算。
（3）目标值变化控制准则。该准则是指在算法迭代过程中，如果在一个给定的步数内，目标值没有改变，则说明如果算法没有其他改进，则解也不会改进，因此，应停止计算。