第１３卷㊀第５期Ｖｏｌ．１３Ｎｏ．５㊀
㊀
智㊀能㊀计㊀算㊀机㊀与㊀应㊀用
ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ
㊀
㊀２０２３年５月㊀
Ｍａｙ２０２３
㊀㊀㊀㊀㊀㊀
文章编号：２０９５－２１６３（２０２３）０５－０１４５－０６
中图分类号：ＴＰ３９９
文献标志码：Ａ
姜博涵，刘㊀翱，邓旭东，任㊀亮，彭琨琨，艾学轶
（武汉科技大学管理学院，武汉４３００６５）
摘㊀要：在疫情防控需求背景下，常规配送模式已不能满足城市内封控地区物资需求，而采用卡车和无人车联合配送的模式，能够在保证未封控地区进行常规配送的同时，在封控区设立无人车站点，由无人车对封控地区的需求点进行无接触配送㊂针对此问题，首先，建立以总运输成本最小化为目标的整数规划模型；其次，采用最大最小距离算法ＭＭＤ，对疫情封控区的需求点进行聚类操作，解决无人车站点的选址问题㊂同时，采用ＰＳＯ算法进行配送路径优化，从而得到两级配送路线㊂研究结果表明，卡车和无人车联合配送可以为疫情背景下的配送模式提供可行㊁有效的方案㊂关键词：后疫情时代；无人车；车辆路径问题；最大最小距离算法；联合配送
Ｏｎｔｈｅｊｏｉｎｔｄｉｓｔｒｉｂｕｔｉｏｎｐｒｏｂｌｅｍｏｆｔｒｕｃｋｓａｎｄｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓ
ｃｏｎｓｉｄｅｒｉｎｇｅｐｉｄｅｍｉｃｃｏｎｔａｉｎｍｅｎｔ
ＪＩＡＮＧＢｏｈａｎ，ＬＩＵＡｏ，ＤＥＮＧＸｕｄｏｎｇ，ＲＥＮＬｉａｎｇ，ＰＥＮＧＫｕｎｋ
ｕｎ，ＡＩＸｕｅｙｉ
（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００６５，Ｃｈｉｎａ）
ʌＡｂｓｔｒａｃｔɔＵｎｄｅｒｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｎｅｅｄｓｏｆｅｐｉｄｅｍｉｃｐｒｅｖｅｎｔｉｏｎａｎｄｃｏｎｔｒｏｌ，ｔｈｅｃｏｎｖｅｎｔｉｏｎａｌｄｉｓｔｒｉｂｕｔｉｏｎｍｏｄｅｃａｎ ｔｍｅｅｔｔｈｅｎｅｅｄｓｏｆｔｈｅｕｒｂａｎｓｅａｌｅｄｃｏｎｔｒｏｌａｒｅａｓｉｎｔｈｅｃｉｔｙ．Ｔｈｅｊｏｉｎｔｄｉｓｔｒｉｂｕｔｉｏｎｍｏｄｅｏｆｔｒｕｃｋｓａｎｄｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓｃａｎｅｎｓｕｒｅｔｈｅｎｏｒｍａｌｒｅｇｕｌａｒｄｉｓｔｒｉｂｕｔｉｏｎｉｎｔｈｅｕｎｓｅａｌｅｄａｒｅａｓ，ｗｈｉｌｅｔｈｅｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓｃａｎｃａｒｒｙｏｕｔｎｏｎ－ｃｏｎｔａｃｔｄｉｓｔｒｉｂｕｔｉｏｎｔｏｔｈｅｄｅｍａｎｄｐｏｉｎｔｓｉｎｔｈｅｓｅａｌｅｄｃｏｎｔｒｏｌａｒｅａｓｂｙｓｅｔｔｉｎｇｕｐｔｈｅｕｎｍａｎｎｅｄｓｔａｔｉｏｎｓｉｎｔｈｅｓｅａｌｅｄｃｏｎｔｒｏｌａｒｅａｓ．Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ，ｆｉｒｓｔｌｙ，ａｎｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｉｓｅｓｔａｂｌｉｓｈｅｄｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｏｆｍｉｎｉｍｉｚｉｎｇｔｈｅｔｏｔａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔ．Ｓｅｃｏｎｄｌｙ，ｔｈｅＭａｘｉｍｕｍａｎｄｍｉｎｉｍｕｍｄｉｓｔａｎｃｅａｌｇｏｒｉｔｈｍ
ＭＭＤｉｓｕｓｅｄｔｏｃｌｕｓｔｅｒｔｈｅｄｅｍａｎｄｐｏｉｎｔｓｉｎｔｈｅｅｐｉｄｅｍｉｃｓｅａｌｅｄｃｏｎｔｒｏｌａｒｅａｔｏｓｏｌｖｅｔｈｅｌｏｃａｔｉｏｎｐｒｏｂｌｅｍｏｆｕｎｍａｎｎｅｄｄｉｓｔｒｉｂｕｔｉｏｎｓｔａｔｉｏｎｐｏｉｎｔｓ．Ｍｅａｎｗｈｉｌｅ，ｔｈｅＰＳＯａｌｇｏｒｉｔｈｍｉｓｅｍｐｌｏｙｅｄｔｏｏｐｔｉｍｉｚｅｔｈｅｄｉｓｔｒｉｂｕｔｉｏｎｒｏｕｔｅ，ｓｏａｓｔｏｏｂｔａｉｎｔｈｅｔｗｏ－ｌｅｖｅｌｄｉｓｔｒｉｂｕｔｉｏｎｒｏｕｔｅ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｊｏｉｎｔｄｉｓｔｒｉｂｕｔｉｏｎｏｆｔｒｕｃｋｓａｎｄｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓｃａｎｐｒｏｖｉｄｅａｆｅａｓｉｂｌｅａｎｄｅｆｆｅｃｔｉｖｅｓｃｈｅｍｅｆｏｒｔｈｅｄｉｓｔｒｉｂｕｔｉｏｎｍｏｄｅｕｎｄｅｒｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｅｐｉｄｅｍｉｃ．
ʌＫｅｙｗｏｒｄｓɔｐｏｓｔ－ｅｐｉｄｅｍｉｃｅｒａ；ｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓ；ｖｅｈｉｃｌｅｐａｔｈｐｒｏｂｌｅｍｓ；ｍａｘｉｍｕｍａｎｄｍｉｎｉｍｕｍｄｉｓｔａｎｃｅａｌｇｏｒｉｔｈｍ；ｊｏｉｎｔｄｉｓｔｒｉｂｕｔｉｏｎ
基金项目：武汉科技大学资助项目（２０２２Ｈ２０５３７）；教育部人文社会科学研究规划基金项目（２１ＹＪＡＺＨ０５０）；国家自然科学基金青年项目
（７１９０１１６７）；武汉市知识创新专项曙光计划项目（２０２２０１０８０１０２０３１７）；
武汉市知识创新专项基础研究项目（２０２２０１０８０１０１０３０１）；中国物流学会㊁中国物流与采购联合会面上研究课题（２０２２ＣＳＬＫＴ３－１３０）；湖北省高等学校优秀中青年科技创新团队计划项目（Ｔ２０２２００３）㊂
作者简介：姜博涵（１９９７－），男，硕士研究生，主要研究方向：物流系统优化；刘㊀翱（１９８７－），男，博士，副教授，主要研究方向：管理优化与决
策；邓旭东（１９６４－），男，硕士，教授，主要研究方向：管理优化与决策；任㊀亮（１９８５－），男，博士，讲师，主要研究方向：管理优化与决策；彭琨琨（１９８６－），男，博士，副教授，主要研究方向：智能优化方法；艾学轶（１９８３－），女，博士，讲师，主要研究方向：供应链库存管理㊂
通讯作者：刘㊀翱㊀㊀Ｅｍａｉｌ：ｌｉｕａｏ＠ａｍｓｓ．ａｃ．ｃｎ收稿日期：２０２２－１２－３０
０㊀引㊀言
新冠疫情爆发以来，全球经济都受到了严重的影响，后疫情时代的到来使各地的防疫形势依然严峻㊂作为中国经济体系的关键部分，物流业某些环
节的薄弱点和不足也显露出来㊂在疫情防控下道路封闭㊁配送链断裂，导致居民生活和物资需求不能得到保障，传统的配送方式已不能满足物流需求㊂针对上述问题，考虑到城市中部分地区封控的情况下，无接触式配送能有效降低病毒传播的风险，卡车和
无人车联合配送能为疫情封控背景下的配送活动提供可行的方案㊂
无人配送近年来广受学者关注，主要用到的工具是无人机和无人车㊂在无人机配送的研究中，
Ｋｕｏ等［１］研究了考虑时间窗的无人机配送路径问题；张梦［２］和王新等［３］研究了车辆和无人机联合配送的优化方法，并设计算法进行求解验证㊂但基于无人机技术的发展受到各地政治㊁经济水平等因素的限制，在实际场所中无法得到广泛的应用㊂相较于无人机，无人车具有更大的优势，已经开始应用到实践中㊂
Ｔａｅｆｉ等［４］认为，电动汽车在配送领域有很大的应用空间，可以很大程度减少运输成本和缓解环境问题；Ｍｉｇｕｅｌ［５］对比了传统燃油车和无人车的碳排放和成本也验证了这一观点；赵国富［６］分析了无人车在普及过程中遇到的问题，并进行案例分析和规划设计；王愚勤［７］和Ｌｉｕ等［８］研究了智联网下的无人车问题；Ｓｏｎｎｅｂｅｒｇ［９］和赵思雨等［１０］在研究无人车在
最后一公里 配送路径问题中，考虑了无人车电池容量和时间窗等因素；陈志强等［１１］提出了一种遗传禁忌混合算法，求解基于无人车的带有时间窗车辆路径问题；施磊［１２］研究了无人车和传统车辆结合的混合车队问题；郑李萍等［１３］设计了４种不同规模的无人车辆服务网络，并仿真分析了车辆配置对于配送网络的影响；孙珊［１４］针对 最后一公里 配送问题，设计了一种卡车携带无人车协同配送的模式㊂
针对疫情封控下的物流配送现实困难，本文提出卡车和无人车联合选址－配送问题，在封控区设立无人车站点，由站点的无人车进行配送，而未被封控的地区保持原有的配送方式不变，并以此为基础建立最小化运输成本目标模型，运用最大最小距离算法（ＭａｘｉｍｕｍａｎｄＭｉｎｉｍｕｍＤｉｓｔａｎｃｅＡｌｇｏｒｉｔｈｍ，ＭＭＤ），对需求点进行聚类操作并选出无人配送站点，使用粒子算法（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）求解配送路径优化问题㊂
１㊀卡车和无人车联合配送优化模型１．１㊀问题描述
假定封控区设立的无人车站点可以提供足够数量的车辆，而无人车站点的位置需要依据封控区需求点的位置去建立，站点的位置一经确定后不发生变化㊂卡车从配送中心出发，如遇到封控区的货物需求不能送达，需要将货物交接到无人车站点，并由站点的无人车进行无接触配送，卡车继续执行配送任务㊂卡车和无人车联合配送路线如图１所示
：
需求点
无人车站点
配送中心
封控区域
图１㊀卡车和无人车联合配送路线图
Ｆｉｇ．１㊀Ａｓｃｈｅｍａｔｉｃｄｉａｇｒａｍｏｆｔｈｅｊｏｉｎｔｄｉｓｔｒｉｂｕｔｉｏｎｏｆｔｒｕｃｋｓａｎｄｄｒｉｖｅｒｌｅｓｓｃａｒｓ
１．２㊀条件假设
本问题为不失一般性，基于以下假设：（１）卡车从配送中心出发，执行配送后必须返回配送中心；
（２）无人车只能从站点出发，执行配送任务后须返回站点；
（３）需求点的需求量为ｑｉ，由于疫情防控货物只能在固定的时间段［ｅｉ，ｌｉ］内到达，无人车站点的时间窗由需求点的最早和最晚时间点决定；（４）卡车和无人车有容量和最大行驶里程的约束；
（５）配送任务中，每个需求点和站点只能被访问一次；
（６）封控区的需求点只能由无人车访问，而卡车只能访问无人车站点和未被封控的需求点；（７）每个无人车站点只对其服务范围内的需求点展开配送㊂
１．３㊀符号说明
本文问题涉及的所有节点（包括配送中心㊁无人车站点㊁客户需求点等）都定义在一张无向图Ｇ＝（Ｎ，Ｅ，Ｆ）上㊂
（１）点集合Ｎ＝｛ＮｋɣＮｖ｝；
其中，Ｎｋ是卡车可到达的点集合，包括配送中心Ｎ０㊁无人车站点集合Ｎｓ㊁未被封控的需求点集合Ｎ１ｋ；Ｎｖ是无人车可到达的点集合，包括无人车站点集合Ｎｓ㊁被封控的需求点集合Ｎ１ｖ㊂（２）卡车行驶的边集合Ｅ＝｛（ｉ，ｊ）｜ｉ．ｊɪＮｋ，ｉʂｊ｝；
其中仅包含卡车可到达两点之间的连线㊂（３）无人车行驶的边集合Ｆ＝｛（ｉ，ｊ）｜ｉ．ｊɪＮｖ，ｉʂｊ｝㊂
６４１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀
其中仅包含无人车可到达两点之间的连线㊂设卡车的集合为Ｋ，无人车的集合为Ｖ㊂其中
卡车的最大行驶里程和载重量分别为Ｌｋ和Ｑｋ；无人车的最大行驶里程和最大载重量为Ｌｖ和Ｑｖ㊂ａ和ｂ
分别代表单辆卡车和无人车的使用成本；ｃｋｉｊ和ｃｖ
ｉｊ分
别表示单辆卡车和无人车从点ｉ到点ｊ的行驶成本㊂ｄｉｊ表示节点ｉ到节点ｊ之间的距离；Ｓｖ表示第ｖ辆无人车的所属站点；ｔｉ表示节点ｉ所需的服务时间；ｑｉ表示第ｉ个点的需求量㊂
根据所述问题，定义ｘｉｊｋ㊁ｙｉｊｖ变量如下：
ｘｉｊｋ＝１㊀
第ｋ辆卡车从节点ｉ行驶到ｊ
０㊀
否则（ｉ，ｊɪＮｋ，ｋɪＫ）{
ｙｉｊｖ＝
１㊀
第ｖ辆无人车从节点ｉ行驶到ｊ
０㊀
否则（ｉ，ｊɪＮｖ，ｖɪＶ）
{
１．４㊀模型构建基于问题描述㊁条件假设和符号说明可构建以下模型：㊀
ＭｉｎＺ＝ａðｊɪＮｋðｋɪＫ
ｘ０ｊｋ＋ｂðｊɪＮｖðｖɪＶ
ｙｓｖｊｖ＋
ðｉɪＮｋ
ðｊɪＮｋ
ðｋɪＫｃｋｉｊｘｉｊｋ＋ðｉɪＮｖ
ðｊɪＮｖ
ðｖɪＶ
ｃＶｉｊｙｉｊｖ
（１）约束条件：
ðｉɪＮｓɣＮ１ｋ
ðｋɪＫ
ｘｉｊｋ＝１㊀∀ｊɪＮｓɣＮ
１
ｋ
（２）ðｉɪＮ１ｖ
ðｖɪＶ
ｙｉｊｖ＝１㊀∀ｊɪＮ１ｖ
（３）ðｉɪＮ１ｖ
ðｋɪＫｘｉｊｋ＝ðｉɪＮ１ｋ
ðｖɪＶ
ｙｉｊｖ＝１㊀∀ｊɪＮ
（４）ðｉɪＮｋðｋɪＫ
ｘｉｊｋɤðｉɪＮｖðｖɪＶ
ｙｉｊｖ㊀∀ｊɪＮｓ（５）ðｉɪＮ
ｋðｊɪＮ１ｋɣＮｓ
ｘｉｊｋｑｉɤＱｋ㊀∀ｋɪＫ
（６）ðｉɪＮ
ｖðｊɪＮ１ｖｙｉｊｖｑｊɤＱｖ㊀∀ｖɪＶ
（７）ðｉɪＮｋðｊɪＮｋ
ｘｉｊｋｄｉｊɤＬｋ㊀∀ｋɪＫ
（８）ðｉɪＮｖ
ðｊɪＮ
ｖ
ｙｉｊｖｄｉｊɤＬｖ㊀∀ｖɪＶ
（９）ðｉɪＮｋ
ｘｉ０ｋ＝ðｉɪＮ
ｋ
ｘ０ｉｋ＝１㊀∀ｋɪＫ
（１０）ðｉɪＮｖｙｉ０ｖ＝
ðｉɪＮｖ
ｙ０ｉｖ＝１㊀∀ｖɪＶ
（１１）
ｔｉ＋ｔ１ｉｊ
－ｔｊɤ（１－ðｋɪＫ
ｘｉｊｋ）Ｍ㊀∀ｉ，ｊɪＮｋ（１２）ｔｉ＋ｔ２ｉｊ
－ｔｊɤ（１－ðｖɪＶ
ｙｉｊｖ）Ｍ㊀∀ｉ，ｊɪＮｖ（１３）
ｅｉɤｔｉɤｌｉ
（１４）
㊀㊀其中，式（１）为总成本最低目标函数，包括卡车和无人车的使用成本和路径成本；式（２）表示每个
无人车站点和未封控需求点只被卡车访问一次；式（３）表示每个封控的需求点只被无人车访问一次；
式（４）表示封控的需求点只能由无人车访问，而未封控的需求点只能被卡车访问；式（５）表示只有卡车对无人车站点进行访问之后，该站点的无人车才能开始执行配送任务；式（６）和式（７）是卡车和无人车最大容量的约束；式（８）和式（９）表示卡车和无人车最大行驶里程约束；式（１０）和式（１１）表示卡车和
无人车完成配送任务后，必须返回配送中心或站点；式（１２）表示卡车满足未封控需求点和无人车站点的时间窗约束；式（１３）表示无人车满足封控需求点的时间窗约束；式（１４）表示配送时间满足时间窗约束㊂
２㊀基于ＭＭＤ算法的无人车站点选址
２．１㊀ＭＭＤ算法的基本原理
最大最小距离（ＭＭＤ算法）是模式识别中一种基于试探的类聚算法，以欧式距离为基础，取尽可能远的对象作为聚类中心㊂其基本思想是对待分类模
式样本集采取以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类㊂结合该算法的基本思想，将被封控的需求点进行聚类处理，确定聚类中心，建立无人车站点㊂２．２㊀算法基本步骤
步骤１㊀在被封控的需求点集合Ｎ１ｖ中任选一个需求点，作为第一个聚类中心ｚ１；步骤２㊀选取距离ｚ１最远的一个需求点为第二个聚类中心ｚ２；
步骤３㊀计算其余需求点到ｚ１与ｚ２之间的距
离，并得出最小值：
ｘｉｊ＝ ｘｉ－ｚｊ ㊀ｊ＝１，２
（１５）ｘｉ＝ｍｉｎｘｉ１，ｘｉ２[]㊀ｉɪＮ１ｋ
（１６）㊀㊀步骤４㊀若：
ｘ１＝ｍａｘｍｉｎｘｉ１，ｘｉ２[][]＞θ ｚ１－ｚ２ （１７）
㊀㊀则选取新的需求点ｏ１作为第三个聚类中心ｚ３，判断是否存在新的聚类中心，若不存在，则转到步骤
６㊂其中，θ为比例系数㊂
步骤５㊀假设存在ｋ个聚类中心，计算各需求
点到各个聚类中心的距离ｘｉｊ，并计算：
ｘ１＝ｍａｘ［ｍｉｎ［ｘｉ１，ｘｉ２， ，ｘｉｋ］］＞θ ｚ１－ｚ２ （１８）
若假设成立，则确定新的需求点ｏ１为新的聚类
中心，继续判断有无新的聚类中心存在，若没有，转到步骤６；
步骤６㊀㊀当判断没有新的聚类中心存在时，
７
４１第５期
姜博涵，等：疫情封控的卡车和无人车联合配送问题研究
将封控区需求点集合按最小距离原则分配到各类中，并计算：
ｘｉｊ＝ ｏｉ－ｚｊ ，ｊ＝１，２， ，ｋ，ｉɪＮ１ｋ（１９）㊀㊀步骤７㊀㊀确定各聚类中心为无人车站点的位置㊂
３㊀基于粒子优化的卡车与无人机联合配送路径优化
㊀㊀粒子算法（ＰＳＯ）是模仿鸟类觅食时的飞行特征，通过模拟鸟类体在一片随机的有边界的区域内寻一块食物并飞行到其所在位置，要制定较好的策略，通过寻离食物最近的鸟，并对其附近进行搜索㊂若将该算法应用到优化问题中，则将每一个鸟当作一个粒子，承载了一个目标函数的适应度值㊂通过制定其飞行速度和方向规则，追寻当前最优粒子，去寻当前解空间中最优目标的位置㊂３．１㊀粒子编码
假设顾客数目为Ｌ，车辆最大使用数为Ｍ，构造粒子位置为２行Ｌ列的矩阵，矩阵由左至右依次为编号１－Ｌ对应的列㊂第一行为顾客对应的车辆编号Ｘｖ，第二行为车辆顺序编号Ｘｒ㊂
现假设有６位顾客，２辆车辆，对应以上定义，一个可能出现的粒子［Ｘｖ；Ｘｒ］如下：
车辆编号：２２１１１２㊀㊀顺序编号：６４２３５１将第１辆车服务的需求点３㊁４㊁５放在一起，第２辆车服务的顾客１㊁２㊁６放在一起，然后按照各个需求点的顺序编号，按从小到大的顺序访问需
求点㊂对上述粒子进行调整，可得到以下配送方案：车辆１㊀０ң２ң３ң５ң０㊀车辆２㊀０ң６ң４ң１ң０
３．２㊀粒子初始化
在粒子位置的初始化时，［Ｘｖ；Ｘｒ］中Ｘｖ和Ｘｒ每个位置的元素分别为区间１－Ｍ和１－Ｌ的随机数㊂对于粒子编码操作中不能判断需求点被服务的次序时，按照Ｘｒ的大小，对次序进行更新㊂
粒子的更新公式如式（２０），为粒子速度的更新公式如式（２１）：
㊀㊀㊀㊀㊀㊀㊀㊀Ｘｋ＋１＝Ｘｋ＋Ｖｋ＋１（２０）Ｖｋ＋１＝ωＶｋ＋ｃ１ｒ１（Ｐｋｉｄ－Ｘｋ）＋ｃ２ｒ２（Ｐｋｇｄ－Ｘｋ）（２１）㊀㊀其中，ｋ表示粒子体的迭代次数；Ｘｋ和Ｖｋ分别表示第ｋ次迭代粒子ｉ的位置和速度；Ｐｋｉｄ和Ｐｋｇｄ分别表示个体最优粒子和全局最优粒子的位置；ｒ１和ｒ２为０ １之间的随机数；ｃ１和ｃ２表示个体和全局学习因子㊂
在粒子速度的初始化中，Ｘｖ对应速度Ｖｖ，Ｘｒ对应速度Ｖｒ㊂则Ｖｖ中每个位置上的元素都应该为－（Ｍ－１） （Ｍ－１）的随机数，Ｖ
ｒ
中每个位置上的元素都应该为－（Ｌ－１） （Ｌ－１）的随机数㊂３．３㊀粒子更新取整与越界处理
基于粒子更新后可能会出现向量中元素不为整数的情况（Ｘｖ不为整数），则需进行向上取整操作，Ｘｒ是顺序向量，体现出大小就行，不需取整操作；而后对Ｘｖ和Ｘｒ中的越界元素进行处理，将越界元素赋值为边界值㊂
３．４㊀局部搜索
为使配送方案满足约束，增加局部搜索算子提高解的质量㊂具体操作步骤如下：
步骤１㊀判断得出配送方案ＶＣ是否满足终止条件，若满足条件转至步骤５，否则转步骤２；
步骤２㊀计算ＶＣ每条线路上车辆开始服务时间ｔｉ与需求点ｌｉ的差值，即违反约束的值，挑出违反约束最大的需求点，记录到一个ｎ行２列的矩阵Ｒ中，第一列为ｎ个违反约束的需求点编号，第二列为违反约束值，如未违反约束，则矩阵中的各个值记为０；转到步骤３；
步骤３㊀若Ｒ中存在正值，出对应的需求点ｉ并移除，得到ＲＶＣ转到步骤４；若Ｒ中所有值都为０，则将违反约束的需求点插入到距离该顾客最近的两个节点中，转到步骤１；
步骤４㊀将矩阵插回到配送方案ＲＶＣ中满足约束且距离增量最小的位置，得到新的配送方案ＶＣ；
步骤５㊀计算目标函数值㊂
４㊀算例分析
本文采用ｓｏｌｏｍｏｎ的测试算例ｃ１０１，使用ｍａｔｌａｂ编写ＭＭＤ算法和粒子算法进行求解；运行的计算机参数配置为１１ｔｈＧｅｎＩｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）ｉ５－１１４００＠２．６０ＧＨｚ２．５９ＧＨｚ㊁ＲＡＭ１６ＧＢ㊁ｗｉｎｄｏｗｓｌ０操作系统㊂
４．１㊀无人车站点的选址
为了简化问题和满足一般性，基于算例，本文假设疫情封控区为图２矩形框内的区域（即横坐标２０ ６０和纵坐标０ ４０的区域）㊂
㊀㊀将比例系数θ设置为０．５，运行ＭＭＤ算法得出可将封控区需求点聚类为３个区域（如图３）㊂其中３个聚类中心为无人车站点的位置，坐标分别为（５０，３５）㊁（３５，５）㊁（２５，３０）㊂
８４１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀
908070605040302010102030405060708090100
配送中心
需求点
需求点纵坐标
需求点横坐标
图２㊀封控区表示图Ｆｉｇ．２㊀Ｔｈｅｃｏｎｔｒｏｌａｒｅａ
10
203040
5060
454035302520151050
封控点横坐标
封控点纵坐标
无人车站点封控需求点
图３㊀聚类结果及选址点表示
Ｆｉｇ．３㊀Ｃｌｕｓｔｅｒｒｅｓｕｌｔｓａｎｄｓｉｔｅｓｅｌｅｃｔｉｏｎｐｏｉｎｔｓｒｅｐｒｅｓｅｎｔａｔｉｏｎ
４．２㊀参数设置
分别计算３个区域需求点的总需求，以节点最早和最晚的时间点为无人车站的时间窗㊂其它参数设置如下：
卡车的最大装载量为２００㊁无人车的最大装载量为５０㊁卡车的车辆最大使用数为２５㊁无人车的最大使用数为５㊁卡车的单位路径成本为１０㊁无人车的单位路径成本为２㊁单辆卡车的使用成本为１００㊁单辆无人车的使用成本为２０㊂４．３㊀计算结果分析４．３．１㊀第一阶段求解
在求解第一阶段配送时参数设置为：惯性因子
ω初始值为１，衰减率为０．９８，ｃ１和ｃ２分别为１．５和２㊂迭代５０次得到的配送路径见表１㊂
㊀㊀算法运行时间为１１０．６５ｓ，求得全局最优总运输成本为８７５３，卡车的使用数目为１０，卡车的总行驶里程为７７５，其中卡车５㊁７㊁１０前往无人车站点执行配送㊂
４．３．２㊀第二阶段求解
求解第二阶段无人车前往封控区需求点的配送
方案参数设置：惯性因子初始值为１，衰减率为０．
９５，ｃ１和ｃ２分别为１．５和２，迭代２０次得到配送路径见表２㊂
表１㊀卡车配送路径表Ｔａｂ．１㊀Ｔｒｕｃｋｄｅｌｉｖｅｒｙｐａｔｈｔａｂｌｅ
车辆行程配送路径
１１０＞２０＞２４＞２５＞２７＞２９＞３０＞２８＞２６＞２３＞２２＞２１＞０２２０＞３２＞３３＞３１＞３５＞３７＞３８＞３９＞３６＞３４＞０
３３０＞９０＞８７＞８６＞８３＞８２＞８４＞８５＞８８＞８９＞９１＞０４
百度无人驾驶汽车４０＞５＞３＞７＞８＞１０＞１１＞９＞６＞４＞２＞１＞７５＞０５５０＞５３＞０
６６０＞９８＞９６＞９５＞９４＞９２＞９３＞９７＞１００＞９９＞０７７０＞７４＞０８８０＞１３＞１７＞１８＞１９＞１５＞１６＞１４＞１２＞０
９
９
０＞８１＞７８＞７６＞７１＞７０＞７３＞７７＞７９＞８０＞０
１０１００＞５２＞０
表２㊀无人车配送路径表
Ｔａｂ．２㊀Ｄｅｌｉｖｅｒｙｐａｔｈｔａｂｌｅｏｆｔｈｅｕｎｍａｎｎｅｄｖｅｈｉｃｌｅ车辆行程配送路径１１５２＞４３＞４６＞４７＞５２
２２５２＞４２＞４１＞４０＞４４＞５２
３３５２＞４５＞４８＞５１＞５０＞４９＞５２
４４５３＞５８＞６０＞５３５５５３＞５５＞５４＞５３６６５３＞５７＞５９＞５３７７５３＞５６＞５３８８７＞６＞７２＞６＞６９＞７４
９
９
７４＞６７＞６５＞６＞６＞６６＞７４
１０１０７４＞６３＞７４㊀㊀算法运行时间为３７ｓ，求得全局最优总运输成本为４８５，无人车的使用数目为１０，无人车的行驶总里程为１９３㊂综上，可得最终求得的全局最优解的总成本为９２２８㊂４．４㊀结果对比
为更好的证明卡车和无人车联合配送的优势，通过计算某一卡车司机和需求点顾客出现感染时造成的疫情传播风险，对两种情况进行对比，表３为传统模式的配送方案㊂
表３㊀传统模式配送路径表
Ｔａｂ．３㊀Ｔａｂｌｅｏｆｔｒａｄｉｔｉｏｎａｌｍｏｄｅｄｉｓｔｒｉｂｕｔｉｏｎｐａｔｈｓ
车辆行程配送路径
１１０＞１３＞１７＞１＞１９＞１５＞１６＞１４＞１２－＞０
２２０＞８１＞７８＞７６＞７１＞７０＞７３＞７７＞７９＞８０＞０３３０＞９０＞８７＞８６＞
８３＞８２＞８４＞８５＞８８＞８９＞９１＞０４４０＞５＞３＞７＞８＞１０＞１１＞９＞６＞４＞２＞１＞７５＞０５５０＞５７＞５５＞５４＞５３＞５＞５８＞６０＞５９＞０６６０＞２０＞２４＞２５＞２７＞２９＞３０＞２８＞２６＞２３＞２２＞２１＞０７７０＞９８＞９６＞９５＞９４＞９２＞９３＞９７＞１００＞９９＞０８８０＞６７＞６５＞６３＞６２＞７４＞７２＞６１＞６４＞６８＞６６＞６９＞０９
９
０＞３２＞３３＞３１＞３５＞３７＞３８＞３９＞３６＞３４＞０１０１００＞４３＞４２＞４１＞４０＞４４＞４６＞４５＞４８＞５１＞５０＞５２＞４９＞４７＞０
㊀㊀假设卡车司机５㊁需求点５７（封控）感染病毒，密接的感染率为４．４１％［１５］，计算一次配送任务中的总传播风险值见表４㊂
９
４１第５期
姜博涵，等：疫情封控的卡车和无人车联合配送问题研究
发布评论