下载掌阅APP，畅读海量书库
立即打开
由于配送车辆优化调度问题是一个组合优化问题，因此，在论述配送车辆优化调度问题的求解算法之前，有必要对组合优化问题及其求解方法做必要的阐述。
所谓组合优化是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数达到最小（或最大）的解，包括离散事件的最优编排、分组、次序和筛选等，是运筹学中的一个经典分支。该问题可用数学模型描述为（以目标函数求最小为例）：
min f（x）
s.t.g（x）≥0
x∈D
式中，f（x）为目标函数，g（x）为约束函数，x为决策变量，D表示有限个点组成的集合。
一个组合优化问题可用参数（D，F，f）表示，其中D表示决策变量的定义域，F表示可行解区域，F={x|x∈D，g（x）≥0}，F中的任何一个元素称为该问题的可行解，f表示目标函数。满足f（x * ）=min{f（x）|x∈F}的可行解x * 称为该问题的最优解。组合优化的特点是可行解集合为有限点集，因此，从理论上讲，只要对D中的有限个点逐一判别其是否满足g（x）≥0的约束并计算其目标函数f（x）的大小，则该问题的最优解一定可以得到。因为现实生产和生活中的大量优化问题是从有限个状态中选取最好的，所以大量的实际优化问题都是组合优化问题。配送车辆优化调度问题也是一个典型的组合优化问题。
组合优化问题一般描述为一个抽象的模型或概念，如果对问题中的参数赋予了具体值，则称为问题的一个实例。
在距离空间中，邻域是指以一点为中心的一个圆。在对光滑函数极值的求解中，邻域是一个非常重要的概念，函数的下降或上升都是在一点的邻域中寻求变化方向。在组合优化中，上述距离邻域的概念已不再适用，但是在一点的附近搜索另一个使目标函数下降的点仍是求解组合优化问题的基本思想。在组合优化中，需要对邻域的概念重新进行定义。
定义2.1：对于组合优化问题（D，F，f），D上的一个映射：N：S∈D→N（S）∈2 D 称为一个邻域映射，其中2 D 表示D的所有子集组成的集合，N（S）称为S的邻域，s∈N（S）称为S的一个邻居。
有了邻域的定义，同样可以定义局部最优解和全局最优解的概念。
定义2.2：若s * 满足f（s * ）≤f（s），其中，s∈N（s * ）∩F，则称s * 为f在F上的局部最优解。若f（s * ）≤f（s），其中，s∈F，则称s * 为f在F上的全局最优解。
对于要使目标函数值达到最小的组合优化问题，传统的求解算法是从一个初始点出发，在邻域中寻找使目标函数值更小的点，最后达到一个无法使目标函数值再下降的点。用这种方法肯定能求得问题的局部最优解，但不一定能求得问题的全局最优解。对组合优化问题设计各种求解算法的目的就是设法求得问题的全局精确最优解或近似最优解。
求解组合优化问题的方法也称为搜索方法，可分为三类，即解析法、枚举法和随机法，如图2.1所示。
图2.1 搜索方法分类图
解析法在问题求解过程中主要使用目标函数的解析性质，如一阶导数、二阶导数等，这一方法又可以分为直接法与间接法。
直接法也称为爬山法，它是根据目标函数的梯度来确定下一步搜索的方向。该方法使用迭代改进的技术，在迭代过程中，一个新点是从当前点的附近的点中选出的，所以它又被称为邻域搜索法。如果新点的目标函数值更好，则该点就变成新的当前点，否则就选择和测试其他当前点的邻近点。如果没有更进一步的可能的改进，则算法终止。对于直接法而言，只有在更好的解位于当前解附近的前提下，才能继续向更优的解搜索。显然这种方法只有对于具有单峰分布性质的解空间才能实施有效的搜索，并得到问题的最优解；而对于多峰空间，用直接法很难找到全局最优解。
间接法则从极值的必要条件出发导出一组方程，然后求解方程组再通过比较求得极值。然而由于导出的方程组一般是非线性的，它的求解是非常困难的。所以，对一些很简单的问题才能使用间接法。
另一种典型的搜索方法是枚举法，也称为穷举法。该方法是通过枚举出可行解集合内的所有可行解的方法来求得问题的精确最优解的，即在一个有限搜索空间中，计算解空间中每个点的目标函数值，且每次计算一个。尽管从理论上讲，每个组合优化问题都可以通过枚举法求得最优解，但枚举是以时间为代价的，有的枚举时间可以接受，有的则不可能接受。许多实际问题所对应的搜索空间都很大，有时甚至在目前最先进的计算工具上都无法求解。
随机搜索方法比上述搜索方法有所改进，该方法又分为盲目随机搜索法和导向随机搜索法。对于盲目随机搜索法，只有当解在搜索空间中形成紧致分布时，它的搜索才有效，但这一条件在实际应用中难以满足，且盲目随机搜索法的效率很低。导向随机搜索法是一种利用随机化处理技术来指导搜索的方法，包括禁忌搜索法、模拟退火法、遗传算法等。禁忌搜索法利用禁忌技术指导搜索，有利于跳出局部最优解。模拟退火法利用随机化处理技术来指导对于最小能量状态的搜索。遗传算法是一种利用随机化技术来指导对一个被编码的参数空间进行高效搜索的方法。
一般来说，组合优化问题通常都有大量的局部极值点，且往往是不可微、不连续、多维、多约束条件且高度非线性的NP难题。因此，精确地求解组合优化问题的全局最优解一般是不可能的。对于这些复杂的组合优化问题，一般都是运用一些启发式算法来得到问题的近似最优解。前面提到的爬山算法、禁忌搜索法、模拟退火法、遗传算法等都属于启发式算法。
组合优化问题一般都含有多个约束条件，如配送车辆优化调度问题就是一个典型的多约束组合优化问题，在采用爬山算法、禁忌搜索法、模拟退火法、遗传算法等启发式算法对其求解时必须对这些约束条件进行处理。由于目前尚未找到一种能够处理各种约束条件的一般化方法，所以在对约束条件进行处理时，只能针对具体应用问题的约束条件的特征，选用不同的处理方法。处理约束条件的方法主要有如下两种：
（1）搜索空间限定法。这种处理方法的基本思想是对算法的搜索空间的大小加以限制，使得搜索空间中的每个点都与解空间中的可行解有一一对应关系。
对一些比较简单的约束条件，有时通过在解的表示方法上着手，就能够达到这种搜索空间与解空间之间的一一对应的要求。用这种处理方法能够在算法中设置最小的搜索空间，所以它能够提高算法的搜索效率。但需要注意的是，除了在解的表示方法上想办法之外，也必须保证在算法迭代过程中经过有关操作算子作用后所产生出的新解的有效性。
（2）对不可行解进行惩罚的方法。这种处理方法的基本思想是：对于不满足约束条件的不可行解，在计算其目标函数值时，处以一个罚函数，从而降低该不可行解的评价值。
如何确定合理的罚函数是这种处理方法的难点之所在，因为这时既要考虑如何度量解对约束条件不满足的程度，又要考虑算法在计算效率上的要求。