下载掌阅APP，畅读海量书库
立即打开
在过去的几十年中，由于路径优化问题在实际问题中的广泛应用，基于经典路径优化问题的各种变形和扩展问题引起了学界的重视。这一类问题通常是在经典路径优化问题的基础上引入一些更加贴近现实的约束条件或是针对某类实际问题的特点。这些附加元素统称为属性（Attributes）。从而，这些路径优化问题的变形和扩展都可以归为多属性路径优化问题（Vehicle Routing Problem with Multiple Attributes），有时也被称为复杂路径优化问题（Rich Vehicle Routing Problem）。
多属性路径优化问题旨在更好地刻画系统中较高层次的运作细节或是决策过程，包括更加丰富的系统结构（多个车场、车队属性和商品属性）、客户诉求（如多周期访问）、车辆运行法规（工作时间限制、载重限制、司机劳动法规），以及决策环境（如交通堵塞）。这些属性的引入极大拓展了路径优化问题的研究领域。由于多种属性的引入，原本复杂的路径优化问题的复杂度进一步加大。原有的精确求解方法多数已不再适用，启发式算法也需要进行改良以适应多属性路径优化问题。
虽然不同属性之间存在一定的差异，但由于其共同特点，一些启发式算法也可以适用于多种不同的多属性路径优化问题。因此，在设计适用于一般的多属性路径优化问题的有效算法时，找到各种属性之间的共性尤为关键。
路径优化问题中的各类属性通常来源于实际问题中的应用，现有文献中所涉及的属性大致可以分为三类：客户和路线的资源分配、排序决策、固定序列的评估。这一分类方式与求解方法有着密切的关系。因为以上三类属性所涉及的多属性路径优化问题需要采用完全不同的求解方法。
（1）客户和路线的资源分配。
该类属性主要涉及将有限的资源（如车辆、车辆种类、车场、服务周期）分配给客户和路线的问题。路径优化问题中属于该类属性的包括：多车场、异质车队、多周期、订单拆分、访问地点附属特性、库存、选址和利润获取。此外，我们需要区分该类属性中的两个亚类。其中一部分属性，如多车场或异质车队，涉及将有限的资源分配到各条路线上。这种情况下，算法需要对整条路线进行调整。而另外一些情况下，如多周期路径优化问题或是库存路径优化问题，多涉及将有限资源分配给客户。此时，如果对整条路线进行调整将导致问题无可行解，因此需要针对每个客户进行调整从而改进求解效果。
（2）排序决策。
这一类属性将直接影响路线的性质和结构，如在考虑回程的路径优化问题中，路线是由去程和回程两类客户序列组成的。在考虑多车场或中转场所的路径优化问题中，路线需要多次经过车场，而在一般路径优化问题中，客户按照一定的标准进行分组，然后司机只需访问每组一次即可。
（3）固定序列的评价。
该类属性将影响路线行程过程中各类约束检测和评估问题，包括其他变量，如服务时间、空闲时间、速度选择、货物摆放的路径优化问题。涉及这一类属性的多属性路径优化问题在现有文献中讨论的较多。较为常见的有：时间窗、分时段路径时长/成本、载重限制、开放路径和工作法规的约束。多数评估类的属性隶属于独立的路径，因此，路线的评估在路径优化问题中是可以独立进行的。当然也有一些连接性的评估属性，如系统协同，需要对多条线路进行协同评价和优化。
下面我们分别从不同的属性维度来分析一下多属性路径优化问题。
（1）客户需求。
路径优化问题中出现的客户需求多种多样。首先，时间窗是各种客户需求属性中最为重要的。时间窗的约束可能是由于客户需求提出的（例如，生产厂商最早可以完成生产的时间，或是客户最晚需要获得商品的时间），也可能是由客户所在的地理位置所限制的（营业时间等）。通常，时间窗包含一个或多个互斥的时间段组合（上下午分别的营业时间）。此外，时间窗也可能取决于送货的运输工具，如大型车辆在进入城市中心区域的时间段是受到限制的。
其次，匹配和先后顺序是另外一个重要的方面。如果某一客户需求包括从一个地点收揽货物，然后去另外一个地点进行配送，并且中间不允许转运的话，同一运输工具需要访问这两个地点。更为复杂的需求场景包含多个收揽和配送业务。因此，路线设计需要满足每个收揽业务都要在其对应的配送业务之前完成。
再次，是配送车辆—司机—客户需求的匹配。根据配送车辆的属性，我们需要选取具有一定驾驶水平的司机进行驾驶，并不是所有的配送车辆和司机都能够对所有的客户需求进行服务。这其中需要多方面技能和属性的精准匹配。
其他的属性包括可选客户需求（该需求不一定必须要满足，但是完成配送可以得到额外的收益）、周期性客户需求（有些客户需求是在一个计划周期内的某些时间段内重复发生，如两周一次而不是每天都有需求）、预期需求（根据历史数据预测的客户可能发生的需求）。此外，利用多种方式来满足同一个客户需求也是实际问题中常见的一个属性。这通常是指将一个客户需求分到多个运输工具上进行配送。这种属性经常出现在多式联运中。
最后，还有一方面的属性是配送车辆的行程依赖于客户需求。这类属性通常是指运输车辆的配送路径由所配送的货物决定。因此，客户需求决定了配送距离和行驶时间。例如，一辆卡车空载时可以通过有限高的桥洞，但是当这辆卡车载满货物时则无法通过这个桥洞。类似的如，一辆载有汽油的货车无法通过水域保护区域，而空载时则可以。
（2）车队。
车队通常指代为完成客户需求所需的资源，这些资源包括各种类型的运输工具和司机。
①运输工具。根据不同的标准，我们可以对运输工具进行分类。主要的标准包括成本、载货限制、行驶速度、当前是否可用、在计划周期开始和结束时的实际和预期位置，以及是否可以访问或通过某条路线。相关的成本分类通常包括使用运输工具的固定成本和与距离、时间、停车相关的可变成本。与距离相关的成本主要指高速公路费；与时间相关的成本可以是线性的也可以是非线性的，通常包括每日付给司机的工资和加班费用。此外，成本通常是根据价格表进行计算的。在优化问题中，惩罚成本通常作为软约束存在，这样可以在搜索过程中允许不可行解的出现。
在货物运输中较为常见的车载限制包括载重、体积和数量等，并且多种约束可以同时存在。行驶速度可以是相同的或者是根据车辆的类型存在差异。行驶速度可能由于载重不同而不同，载重越大，速度越慢。此外，行驶速度可以在整个计划周期保持不变，也可能由于所处时间段不同而发生变化。这对于在城市内部发生的短途运输尤为重要，通常上下班高峰时段的行驶速度较慢。运输工具当前的可用性也会受到各种因素的限制，如定期维修或是周日禁止重型车辆进入城市。
在具体的运作层面，尤其是短期计划中，车辆的初始位置通常是给定的，但在策略层面，即中期计划中，决定一个合适的出发地点是很重要的。而对于计划周期结束时车辆的位置通常没有限制。对于车辆类型及所配备的技术设备，通常有不同的标准来判断车辆是否可以完成某个客户需求。这些标准包括车辆类型（卡车、火车等），车辆的长度和载重也会影响其所能配送的路线。同时，尾气排放现在也对配送路径的选择有所影响。各种类型和级别的车辆数量也是至关重要的。在实际情况下，各类车辆的数量是有限的。但对于优化问题而言，在中期计划中，车队规模和构成通常认为是没有限制的。
②司机。对于司机而言，其资质在一定程度上限制了司机与车辆及司机与客户需求的匹配。这些资质通常包括：驾驶执照的类型、是否经过特殊培训（如运输危险货物），以及对特定地区和客户的了解程度。另外一个极为重要的方面是与司机相关的法律经验。在欧盟和其他一些地区，有大量对司机工作和休息时间的限制。车载监控设备可以实时监测司机的状态，从而判断其是否遵守这些法律法规。除了强制性法律法规外，欧盟还颁布了一些可选择的司机规则。但这些都使得路径优化问题的建模更加复杂。
（3）路线结构。
一部分路线结构仅仅针对单条路线，而另外一些路线结构则是关注路线之间的相互关系。对于单条路线而言，标准形式是封闭路线，即路线从同一地点开始和结束。但有些情况下，开放型路线，即路线可以在任意地点结束，也会在实际中得到应用。例如，在长途运输中，通常运输车辆整个星期都在路上，但路径安排是每天进行的；而对于短途运输也可以对多条线路进行规划。
此前的假设是路线之间相互独立，即一个路线的可行与否并不影响其他线路。但有些情况下，多条路线之间存在相互关系，需要各个路线之间的协同。在这种情况下，一条路线的可行与否就会对其他路线产生影响。多线路协同通常跟空间、时间、载重，以及一些稀有资源相关。一个典型的例子就是“视觉吸引”路线计划，即路线之间不能存在交叉。路线协同通常发生在多层级城市物流配送系统中。例如，第一层级的大型车辆需要在分销中心将货物分装到多个小型车辆，从而运送到城市中心的终端客户。另外一个例子是对司机和运输车辆的匹配。在计划周期中，一辆车可能由多个司机轮流驾驶进行配送服务，或者一个司机按顺序驾驶多辆车进行配送。这都可以在一定程度上提高运输车辆和司机的利用率。
此外，在存在转运的情况下，多条线路之间存在相互关系。这包括货物的分配和整合，以及多种模式的运输系统。同时，路线之间的资源约束，如车辆的容量和协同要求，也是一个需要考虑的因素。最后，路线之间工作量的平衡也是实际中的一个因素，这包括各条路线的距离、时长、服务客户数量和成本等。
（4）目标函数。
目标函数可以是单一的，也可以是多方面的。常见的单一目标函数包括使用车辆数量最小化，总行驶距离最短，总成本最小等。如果并不需要服务完所有客户，则目标函数也可以是最大化总收益。
当目标函数包含多个维度时，通常我们考虑对其进行加权平均，即根据各个维度的优先级别对其进行分配权重，或是通过帕累托最优来求解多目标优化问题。有一个值得注意的问题是，前面提到的约束可以分为硬约束和软约束。通常硬约束不可以违反，如逻辑约束或者法律约束。而违反软约束则依然可以得到可行解，但通常将其违反程度作为惩罚函数加入到目标函数中去，违反程度越大，惩罚越大。如果违反程度超过某一阈值，则将变为硬约束，从而导致解不可行。时间窗的约束通常被看作是软约束。