2021-4-9 | 电子商务
从定性分析的角度来看，可以将专家判断以数值形式表示，再经过综合分析后对选址进行决策。首先，根据影响物流设施选址的因素，建立备选方案的评价指标体系；然后，采用一定的评价方法（例如：偏好理论、权重因素分析方法、专家评分法、层次分析法、模糊层次分析法、模糊综合评判法等）得到所需的评价指标的权重；最后，通过求出各备选方案的优劣排序，得到最优方案[1~4]。车辆路径问题是物流配送中的另一个重要问题。一般定义为：对一系列发货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（例如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。在实际应用中，车辆路径问题可以按照不同的分类原则细分为许多子问题。多数的研究都是只针对1~2个属性的问题展开[5~7]。由于这些组合问题多是NP难的，使用动态规划、分支限界、回溯方法进行求解的确定性算法难以避免计算中的组合爆炸。因此，当问题规模稍大时，这类算法在应用中就难以发挥作用，目前的应用中多采用启发式算法和近似算法求解。
电子商务物流组合优化问题的参数算法研究
参数理论研究
从一个更开放的角度来看，电子商务物流系统中的诸多问题可以归约到更多的算法问题上去。例如，物流配送中心选址实际上可以归约到一些覆盖和支配问题以及斯坦纳（Steiner）问题上去，车辆路径问题可以归约到哈密尔顿回路问题和旅行商问题上去，而库存控制和车辆装载可以归约到背包和装箱问题上去。这些问题中很多已经被证明为NP难问题。同时，这类问题很多都与物流网络的拓扑特性有关，多数都来自于图论中的一些经典问题，但不同的是，由物流应用导出的问题往往会在原始图问题的基础上附加一些新的约束条件，例如费用、路线、时间等方面的约束，这些约束有时还会给原问题带来复杂度的增加。尽管多数这类问题都是NP难的，但是问题本身的重要性和挑战性还是引起了研究人员的广泛关注。如前面提到的一些选址和路径问题就是近年来研究得比较多的问题。由于难以求得精确解，研究人员通常设计启发式算法和近似算法求解，在某些场合也取得了较好的效果。尽管如此，但很多时候启发式算法和近似算法得到的结果无助于我们深刻地理解问题的本质，也难以准确评价算法在应用中的实际性能。对此，我们的想法是将参数算法设计和分析理论引入到电子商务物流优化问题的求解中，将电子商务物流中的一些组合优化问题进行参数化建模，进而采用参数算法设计的一些技术设计可行的参数算法来求解这些优化问题。
参数理论的研究最初来源于观察到很多计算问题都与一个取值范围较小的重要参数相联系，利用参数的性质可以在一定程度上加速计算。当一个参数问题可在时间f（k）nc内解决，其中c是一个常数，而函数f独立于输入规模n，则称该问题是固定参数可解的（FixedParameterTractable，FPT），用FPT表示该类问题的集合。根据这一定义，对于小的参数值，FPT问题是实际可解的。根据现有的研究结果，利用参数方法来解决组合优化问题已被证明有着广泛的应用。因此，即使这些计算问题在其一般形式下是NP难的，其实际应用中的实例却有其特殊性。很多计算优化问题都可参数化，且其参数值仅在一个很小的范围内变化。对于这些NP难问题的参数化求解也取得了令人瞩目的成绩。例如，与电子商务物流选址问题相关的一个经典的NP完全问题—点覆盖问题的参数化定义就是：给定一个图G（V，E）和一个整数k，|V|=n，判断图G是否存在一个有k个点的集合C哿V，使得图G中的所有边至少有一个端点在C中。在参数计算与复杂性理论中k（k<<n）被看作是一个参数。利用参数k，人们提出了实际有效的算法，在实际应用中取得了很好的效果。1993年Buss和Goldsmith首次提出针对点覆盖的复杂度为O（kn+2kk2k+2）的算法[8]，而目前最好的算法是有Chen给出的时间复杂度为O（kn+13.285k）的算法[9]。上述算法的求解策略往往都是将参数化问题核化到一个更小的核上，然后再在核上采用分支限界等技术求解。同样，对于在电子商务物流中有着广泛应用的支配集问题的参数化求解也取得了重要的进展。研究表明，参数化支配集问题不是FPT可解的。但是将参数化支配集问题限定在平面图这样一个背景下，则平面图支配集问题可以在O（c姨k?n）时间求解[10]，其中c≤4346姨，随后，常数c的上界又被优化到215.13[11]。最近的研究表明，在平面图上求解支配集，通过两个图规约和预处理技术，可以得到一个不超过335k大小的核[12]，这个线性核完全独立于原始图的规模。由于k相对n通常是很小的数，问题的规模就从降低到的线性函数，这也就大大降低了问题的规模。因此参数算法技术在一些组合优化问题的求解上是极其有益的。
电子商务物流组合优化问题的参数算法研究
针对电子商务物流中的一些组合优化问题，可以首先从参数算法的角度对这些问题建模，然后设计有效的参数算法求解，最后将这些参数算法转化为适合于实际应用环境的近似算法。具体来说可以采用如下方法。（1）电子商务物流问题的参数化。对电子商务物流中的优化问题的不同参数化会导致差异巨大的参数复杂性，特别是，如果不适当的进行参数化，则问题可能变成参数不可解的。因此，需要注意的是如何将物流中的优化问题正确的参数化，使得参数化后的计算问题满足如下两点条件：①参数化的计算问题仍能够反映原问题的本质。②参数化计算问题使得小参数算法的方法可以有效地应用并解决原问题。值得注意的是，由于物流网络的复杂性和本身固有的其他约束，电子商务物流网络优化问题中必然会存在某些无法用参数算法解决或不能够用参数算法很好解决的问题。对于这一类问题，我们还需研究一套行之有效的方法，使得能够解决或部分解决参数化问题。（2）电子商务物流优化问题的参数算法设计及性能分析。利用参数问题的特殊性来研究与传统算法技术不同的参数算法设计与分析的新技术将对有效使用参数算法在电子商务物流优化问题中的应用有着非常重要的影响。一旦优化问题参数化以后，利用参数值的特殊性，以及其对整个计算问题复杂性的影响，特殊的参数算法技术可能大大改善解决问题的效率，而达到传统算法无法达到的效果。这一方面的研究所遇到的挑战是如何从传统算法设计的框架中跳出来，设计崭新的行之有效的参数算法及其分析技术。通过利用参数理论中发展起来的一些算法设计技术，例如核化、有限搜索树、分解规约等，设计一些可行的参数算法来求解这些算法优化问题。参数算法得到的精确解可以更深刻的理解优化问题本质，对其他启发式算法和近似算法的评估也有着重要的意义。（3）电子商务物流优化问题的近似算法设计与分析。在前述参数算法的基础上，通过一些改进和简化，设计一些更适合于实际应用场合的近似算法。在以往的研究中我们注意到，参数理论中发展起来的很多规约和预处理技术不仅仅可用于参数算法设计，在近似算法中同样有着重要的作用。在一些场合，这些技术能迅速化简问题，降低问题的复杂度，无论是在理论上还是在实际应用场合。同时对这些近似算法和分布式算法的分析可以采用平摊分析技术。在以往的物流优化问题研究中，对算法的分析和评价主要以最坏情况分析和仿真实验比较居多。最坏情况分析在某些问题上无法客观地评价算法性能，而仿真实验的说服力有限。例如经典的快速排序算法，它的最坏情况是相对较差的，但是它的平均性能却是所有排序算法中最好的。因此在某些应用场合一些近似算法往往比一些确定性算法（或者有理论下界保证的算法）具有好得多的平均性能。这是对这些算法进行平摊分析的一个重要原因。