带外包的服饰运输调度问题的优化

杨 军 蔡延光 汤雅连 江泽东

（广东工业大学 自动化学院，广州 510006）

带外包的服饰运输调度问题的优化

杨 军 蔡延光 汤雅连 江泽东

（广东工业大学 自动化学院，广州 510006）

由于服饰产品是一种时效性很强的商品，而且服饰产品在配送过程中可以外包给快递公司进行配送，对带外包和硬时间窗的服饰运输调度问题（Apparel products Vehicle Routing Rroblem with Hard Time Windows and Outsourcing，AVRRHTWO）进行分析，并构建了AVRRHTWO、一般性VRR（Vehicle Routing Rroblem）和VRRSTW（Vehicle Routing Rroblem with Soft Time Windows）的数学模型，通过对基本的人工鱼群算法（artificial fish swarm algorithm，AFSA）进行改进，混沌搜索被引入人工鱼群算法来提高算法的全局收敛性，反馈策略用来指导人工鱼的移动，以此来提高收敛精度。应用混沌人工鱼群算法（chaotic artificial fish swarm algorithm，CAFSA）及遗传算法（genetic algorithm，GA）对所建立的三种模型求解，通过对实验数据进行处理，证明了AVRRHTWO模型和混沌人工鱼群算法求解此类模型的有效性，进一步证明了问题模型的复杂程度影响算法寻优能力，问题模型简单时，遗传算法更优；问题模型复杂时，混沌人工鱼群算法更优。

硬时间窗；软时间窗；外包；服饰运输调度问题；混沌人工鱼群算法；遗传算法

服饰产品是一种时效性很强的商品，流行周期短，季节性强，一旦过了季节或者流行期，销售转弱，价格会大幅下降，且具有变化快、多品种，以及强烈的地域性消费差异等特点，这就要求服饰企业的物流配送必须做到及时、准确，能够尽快缩短交货周期，也就是要求企业拥有较强的过程控制能力和供货时效性，能够准确按照客户需求准时准确地做到物流服务。由于地域性消费差异，不同门店的需求也不一样，所以企业在配送过程中，对大批量的服饰可以采用厂家直销直接配送的方式，对小批量的服饰可以外包给快递公司配送的方式，最终目的就是最小化成本。

华铨平等人［1］分析服装具有时效性强等特点，建立了服装时效性的模糊数学模型，提出的改进的蚁群算法，证明了改进算法对具有时效性服装VRR模型求解的合理性与有效性；王赟等人［2］研究了服装配送网络中的车辆路径优化问题，验证了遗传算法求解该问题模型的可行性和优越性；贾祥素等人［3］提出了改进的蚁群算法求解服装运输车辆路径规划问题，取得了良好成果；王昕等人［4］研究了一种适合服装供应链VRR成本模型的奖惩蚁群算法，证明了该模型与求解算法的有效性；王培崇等人［5］对一般的VRR进行分析，在初期阶段应用人工鱼群算法迅速获得阶段最优解，后期应用遗传算法寻优，证明了算法具有求解速度快、性能稳定等优点；朱命昊等人［6］采用随机键表达编码的改进人工鱼群算法对旅行商问题求解，算法测试表明改进的算法提高了收敛速度，增强了全局搜索能力。通过混沌人工鱼群算法求解AVRRHTWO的文献不多，所以本文重点是通过混沌人工鱼群算法求解AVRRHTWO模型，并比较该算法和遗传算法求解该模型和其他两种模型的效果。

1 问题描述及数学模型的建立

1.1 问题描述及假设

带外包的硬时间窗服饰运输调度问题是指对于一系列需求点，给定车场位置以及客户的数量、位置和需求量，组织适当的运输路线，使服饰配送在满足一定的约束条件（运输容量、硬时间窗、里程约束及载重约束等）下，达到运输成本最少的目的。本节研究的问题基于以下假设：1）1个工厂，1个快递公司，l个门店（i，j=1，2，…，l），门店需求确定；2）车辆有最大里程约束、载重约束，同种车型；3）硬时间窗约束；4）车辆的配送任务完成后必须回到车场。

1.2 建立AVRPHTWO的数学模型

有l个门店，第i个门店的需求量为gi，从工厂将服饰配送给各门店，门店要求送货时间窗为［Ai，Bi］，门店i与j之间的距离为dij。Ti表示车辆到达i的时间。可以按照式（1）估算车辆数。式中，［］表示不大于括号内数字的最大整数；0＜α＜1，是对装车（或卸车）的复杂程度及约束多少的估计。tij表示从i到j的行驶时间，T总表示行驶总时间。

配送方式有以下两种。

1）工厂配送。假设工厂由货车配送，货车载重为qc，速度为vc，有m辆货车，已知gi＜qc，cijk表示为车辆k将服饰从点i送到点j的单位运价，nk表示第k辆车服务的门店个数，ck为启用车辆的固定成本，Dmax为货车的里程约束。

2）快递配送。假设快递公司由摩托车配送，摩托车载重为qd，有s辆货车，c1为起价，c2为续价，ph表示第h辆车服务的门店个数，Dh为摩托车的里程约束。

定义变量如下

建立数学模型：

目标函数

约束条件

目标函数式（6）表示总运输成本最低，由两部分构成，工厂自销配送费用与外包给快递公司的配送费用之和；（7）为车辆行驶距离约束，其中dijk表示车辆k行驶了门店i到j的路程，dijh表示车辆h行驶了门店i到j的路程；（8）表示车辆完成任务后，回到原车场；（9）表示当某辆车配送到门店的个数大于等于1时，则参与了配送服务，否则，没有参与配送；（10）表示所有门店都被服务到；（11）表示不能超过车辆的载重；（12）表示保证每辆车服务的门店总数小于等于总门店数目；（13）表示到达门店i的时间必须在时间窗内；（14）表示到达j的时间Tj为车场到i的时间T0i与门店i到门店j的时间tij之和。

1.3 建立VRP的数学模型

按照1.2节方法估算车辆数。本节考虑简单的VRR模型，只研究厂家直销的配送模式。对1.2节进行简化：不考虑外包配送模式和时间窗约束。目标函数及约束的表述见1.2节。

定义变量如下：

建立数学模型：

目标函数

约束条件

1.4 建立VRPSTW的数学模型

在1.3节的基础上加上软时间窗约束，即考虑VRRSTW模型，β为车辆早到和晚到的惩罚系数，目标函数包含了运输成本和时间窗惩罚费用。时间窗约束见1.2节，约束条件极其表述见1.2节和1.3节。

建立数学模型。

目标函数：

2 混沌人工鱼群算法

2.1 求解思路

人工鱼群算法［7］是模拟鱼群的行为进行随机的搜索，主要利用人工鱼的觅食、聚群、追尾等行为，利用局部最优信息逐步达到全局寻优的目的。为了提高人工鱼群算法的全局搜索能力，克服基本人工鱼群算法精度低、后期收敛慢、复杂度较高等特点，本文主要是采用基于混沌搜索和反馈策略的混沌人工鱼群算法解决服饰物流运输调度问题。

2.2 混沌人工鱼群算法求解步骤

鱼群中，每个个体的位置向量X=（x1，x2，…，xn），X为寻优决策变量；人工鱼个体i与个体j间的距离表示为di，j=Xj-Xi；人工鱼当前所在位置的食物浓度为Y=f（X），即为目标函数值；Visual表示人工鱼的感知距离；step表示人工鱼的感知距离；δ为拥挤度因子；α为衰减因子，Pf为反馈概率；Try-num表示人工鱼每次移动的最大试探次数。在寻优过程中，X中元素的顺序表示配送的访问顺序，也就是一个潜在的解，其适应值可以衡量解X的优劣程度。由于混沌搜索具有随机性、遍历性和确定性，所以混沌搜索要比随机搜索好。

1）混沌搜索。文中选用Logistic映射［8-10］，如式（28）所示。式中，i表示混沌变量的序号，i=1，2，…，r；u表示种群序号，u=0，1，…，n=0；βi表示混沌变量，0≤βi≤1；μi表示吸引子。当μi=4时，Logistic映射完全处于混沌的状态，此时产生的混沌变量βi具有很好的遍历性。假设迭代次数为300，初值为0.6，得到Logistic映射的概率分布图，如图1所示。

2）反馈策略。每条人工鱼执行完移动操作后会检验自身状态与公告牌的状态，若自身状态优于公告牌状态，则用自身状态代替原公告牌状态，这样公告牌就可以记录下历史最优状态。基于这一思路，为人工鱼定义一个新行为——反馈行为，即人工鱼向公告牌记录的最优状态移动，人工鱼以一定的概率执行该行为。

对人工鱼群算法进行改进，设置反馈概率Pf，人工鱼以概率Pf执行随机行为，以概率1-Pf执行反馈行为。优化过程开始时赋予Pf一个较大的数，随着优化过程的进行Pf按式（29）逐渐减小，α为反馈概率的衰减因子。

3）觅食行为。设人工鱼i当前状态为Xi，在其感知范围内随机选择一个状态Xj，如式（30）。

其中，rand（）是一个介于0和1之间的随机数，若Yi＞Yj，则向该位置和全局最优位置Xbest-af的向量和方向前进一步；反之，再重新随机选择状态Xj，判断是否满足前进条件，若满足，则按式

（31）前进一步；若不满足则继续试探，反复尝试Try-num次后，如果仍不满足前进条件，则按式

（32）随机移动一步。

4）聚群行为。人工鱼探索当前邻域内（即dij＜Visual）伙伴数目nf及中心位置Xc。如果Yc·nf＜δ·Yi，表明伙伴中心有较多食物且不太拥挤，那么按式（33）朝伙伴的中心位置和全局最优位置Xbest-af的向量和方向前进一步，否则执行觅食行为。

5）追尾行为。人工鱼探索当前邻域内（即dij＜Visual）的伙伴中Yj为最小的伙伴Xj。如果Yj·nf＜δ·Yi，表明伙伴Xj具有较高的食物浓度并且其周围不太拥挤，那么式（34）朝Xj的方向和全局最优位置Xbest-af的向量和方向前进一步，否则执行觅食行为。

6）随机行为。随机行为是为了在更大范围内寻觅食物或同伴，随机选择一个状态，然后向该方向移动。

混沌人工鱼群算法的步骤如下：

Step1：进行初始化设置：人工鱼的感知距离Visual、人工鱼的感知距离Step、拥挤度因子δ、衰减因子α、反馈概率Pf、人工鱼每次移动的最大试探次数Try-num和最大迭代次数MAXGEN。

Step2：计算每条人工鱼的适应度值，将最优的人工鱼状态记入公告牌。

Step3：对每条人工鱼进行评价，对其要执行的行为进行选择，包括觅食行为、群聚行为、追尾行为。若执行后的状态优于当前状态，则向更优状态的方向前移一步，然后转至Step5。

Step4：随机产生一个数，若rand（）＜Pf，则执行随机行为，否则执行反馈行为。

Step5：最优人工鱼执行混沌搜索。

Step6：更新公告牌和反馈概率。

Step7：若满足循环结束的条件则输出结果，否则转至步骤（3）。

3 仿真分析

某市的服饰厂家向市内各区门店供应服饰。所有门店的信息如表1所示。

工厂配有车场，工厂位置为（50，50），货车的最大配送里程为300 km，货车速度为50 km/h，载重为15 t，工厂送货最早出发时间为5:00，货车运费为1元/km，起步价为40元/辆，不考虑卸货时间，有同类型的货车若干。软时间窗VRR中，早到和晚到的惩罚β为10元/h。

快递公司位置为（50，80），摩托车的最大配送里程为250 km，摩托车车速60 km/h，载重为300 kg，快递公司起价为0.01元/t，续价为0.001元/t，不考虑卸货时间，快递公司最早出发时间为6:00，有同类型的摩托车若干。

算例分析

AVRRHTWO模型的求解结果见表2。厂家派出4辆车配送，外包给快递公司的配送任务由2辆车配送，总配送距离为758.29 km，总配送费用为823元，最优配送网络如图2，应用两种算法的收敛情况如图3，可见CAFSA在第10代就收敛到最优解，而GA在40代才收敛到最优解，CAFSA优于GA。

VRR模型的求解结果见表3，由4辆车配送，最优配送距离为650.71 km，总配送费用为810.71元，最优配送网络如图4，应用两种算法求解VRR问题模型的收敛情况如图5所示，GA在第8代收敛，CAFSA在第30代收敛，GA优于CAFSA。VRRSTW模型的总配送费用为903.71元，最优配送方案如表4，最优配送网络与VRR的一致，应用两种算法求解VRRSTW的收敛情况如图6所示，GA在第20代收敛，CAFSA在第15代收敛，CAFSA略优于GA。

可见问题模型简化后，最优结果发生变化。当不考虑时间窗时，送货时间相对宽松，无需外包给快递公司，所以总配送费用略有降低。当加上软时间窗后，由于送货早到或者晚到的惩罚成本，总配送费用也相应增加。

4 结语

本文通过对带外包和硬时间窗的服饰运输调度问题进行分析，构建了AVRRHTWO和一般性VRR的数学模型。混沌搜索被引入人工鱼群算法来提高算法的全局收敛性，反馈策略用来指导人工鱼的移动，这样就形成了混沌人工鱼群算法，应用该算法及标准的遗传算法对所建立的两种模型求解，比较不同算法求解不同模型的结果，证明了AVRRHTWO模型和CAFSA求解此类模型的有效性，也表明了问题模型的复杂程度影响求解结果。

［1］ 华铨平，王昕.时效性服装配送模型与改进蚁群算法的研究［J］.纺织学报，2012，33（6）：139-133.

［2］ 王赟，李仁旺，倪夏静，等.基于遗传算法的服装配送路径优化策略［J］.浙江理工大学学报，2013，30（2）：178-183.

［3］ 贾祥素，吴菁.基于改进蚁群算法服装运输车辆路径优化研究［J］.浙江纺织服装职业技术学院学报，2013（3）：67-72.

［4］ 王昕，华铨平.基于服装供应链与服装属性的VRR成本模型［J］.西安工程大学学报ISTIC，2012，26（6）：756-760.

［5］ 王培崇，钱旭，周玉.求解VRR问题的混合鱼群遗传优化算法［J］.计算机工程与应用，2009，45（24）：201-203.

［6］ 朱命昊，厍向阳.求解旅行商问题的改进人工鱼群算法［J］.计算机应用研究，2010，27（10），3734-3736.

［7］ 江铭炎，袁东风.人工鱼群算法及其应用［M］.北京：科学出版社，2012.

［8］ Hu W，Liang H，Reng C，etal.A Hybrid Chaos-Rarticle Swarm Optimization Algorithm for the Vehicle Routing Rroblem with TimeWindow［J］.Entropy，2013，15（4）：1247-1270.

［9］ Yue Y X，Wen Z B，Yue Q X.Chaos Optimization Algorithm for Vehicle Routing Rroblem［J］.Advanced Materials Research，2012，538：2722-2726.

［10］ 汤雅连，蔡延光，郭帅，等.单车场关联物流运输调度问题的混沌遗传算法［J］.广东工业大学学报，2013，30：53-57.

Optimization for Apparel Transportation Scheduling Problem with Outsourcing

YANG Jun CAIYan.guang TANG Ya.lian JIANG Ze.dong
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

Apparel product，as a strong timeliness goods，can be outsourced by the Express Company in the process of delivery.This paper analyzes the Apparel products Vehicle Routing Rroblem with Hard Time Windows and Outsourcing（AVRRHTWO），and then builds the AVRRHTWO model，Vehicle Routing Rroblem with Soft Time Windows（VRRSTW）model and general mathematicalmodel of Vehicle Routing Rroblem（VRR），improving the basic artificial fish swarm algorithm（AFSA），introducing the chaotic search in order to improve the global convergence of the artificial fish swarm algorithm，using feedback strategy to guide themovement of the artificial fish，in order to improve the convergence precision.By way of chaotic artificial fish swarm algorithm（CAFSA）and genetic algorithm（GA）to solve the three kinds ofmodel，based on the experimental data processing，it can prove the validity of AVRRHTWOmodel and the chaotic artificial fish swarm algorithm to solve the kinds ofmodel；moreover，it further proves that the complexity of themodel can affect the optimization ability；the simpler the problem model is，the better genetic algorithm is；themore complex the problem model is，the better chaotic artificial fish swarm algorithm is.

hard timewindows；Soft TimeWindows；outsourcing；apparel products Vehicle Routing Rroblem；chaotic artificial fish swarm algorithm；genetic algorithm

TR301

码：A

：1009-0312（2014）05-0034-08

2014-03-18

国家自然科学基金（61074147，61074185）；广东省自然科学基金（S2011010005059，8351009001000002）；广东省教育部产学研结合项目（2012B091000171，2011B090400460）；广东省科技计划项目（2012B050600028，2010B090301042）。

杨军（1989—），男，湖南株洲人，硕士生，主要从事嵌入式软件开发研究。