Nothing Special   »   [go: up one dir, main page]

CN118134372A - 基于一单多商情形下的城市电商外卖配送路径优化方法 - Google Patents

基于一单多商情形下的城市电商外卖配送路径优化方法 Download PDF

Info

Publication number
CN118134372A
CN118134372A CN202410221081.1A CN202410221081A CN118134372A CN 118134372 A CN118134372 A CN 118134372A CN 202410221081 A CN202410221081 A CN 202410221081A CN 118134372 A CN118134372 A CN 118134372A
Authority
CN
China
Prior art keywords
operator
cost
delivery
take
takeaway
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202410221081.1A
Other languages
English (en)
Inventor
肖建华
陈亮
张文雪
牛旭东
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nankai University
Original Assignee
Nankai University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nankai University filed Critical Nankai University
Priority to CN202410221081.1A priority Critical patent/CN118134372A/zh
Publication of CN118134372A publication Critical patent/CN118134372A/zh
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/083—Shipping
    • G06Q10/0835—Relationships between shipper or supplier and carriers
    • G06Q10/08355—Routing methods
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06311—Scheduling, planning or task assignment for a person or group
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06315—Needs-based resource requirements planning or analysis
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q30/00—Commerce
    • G06Q30/06—Buying, selling or leasing transactions
    • G06Q30/0601—Electronic shopping [e-shopping]
    • G06Q30/0633—Lists, e.g. purchase orders, compilation or processing
    • G06Q30/0635—Processing of requisition or of purchase orders
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/10—Internal combustion engine [ICE] based vehicles
    • Y02T10/40—Engine management systems

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Marketing (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Development Economics (AREA)
  • Theoretical Computer Science (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Educational Administration (AREA)
  • Accounting & Taxation (AREA)
  • Game Theory and Decision Science (AREA)
  • Finance (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开一种基于一单多商情形下的城市电商外卖配送路径优化方法，一单多商指外卖顾客同时在不同商家下单的消费场景，包括以下步骤：S1.基于配送路径成本、发车成本、顾客满意度损失成本及若干约束条件构建外卖配送优化模型，目标函数为总成本最小；总成本为配送路径成本、发车成本、顾客满意度损失成本的和；S2.设置参数；S3.初始化，利用节约法产生初始解，并初始化选择不同移除算子与插入算子的概率；通过ALNS算法不断地移除和不断地重新插入以改进初始解，当获得的新解得到改进或者满足接受解规则，下一次迭代中的初始解用当前的新解代替，最终完成迭代。

Description

基于一单多商情形下的城市电商外卖配送路径优化方法
技术领域
本发明涉及外卖配送路径优化领域，特别是涉及一种基于一单多商情形下的城市电商外卖配送路径优化方法。
背景技术
随着外卖行业的发展与成熟，降低配送成本、提高顾客满意度已经成为外卖企业的核心竞争战略。然而，在当前“一单多商”的消费背景下，由于配送经验不足、配送难度大、配送服务要求高，使得外卖配送资源配置不合理、外卖配送服务达不到要求，外卖平台正面临着配送成本居高不下、外卖顾客用餐体验不足的双重考验。因此，如何将外卖配送资源进行合理配置，优化配送路径，进而降低配送成本、提高顾客满意度，已经成为外卖企业亟待解决的问题。
城市外卖最近几年发展迅速，市场规模稳步扩大。“一单多商”指的是外卖顾客同时在不同商家下单的消费场景。随着消费的升级以及“聚会经济”的盛行，外卖顾客的用餐需求已经不再局限于单一商家或者单一外卖商品，呈现出多样化、个性化的跨商家消费特点。为了满足外卖顾客的用餐需求、提供更优质的服务，进而提高自身竞争力，各外卖企业都推出了新的产品或服务。美团推出智能点餐服务，提供适合不同数量、不同价位人群的用餐组合，为外卖顾客的个性化组合消费提供了参考；饿了么推出购物车一键结算服务，外卖顾客可以一次在多个商家消费，为外卖顾客跨商家消费提供了便利；饿了么与美团外卖都推出了同城“跑腿”业务，通过为外卖顾客提供帮买帮送服务，极大程度上满足了外卖顾客跨商家的用餐需求。可以看出，外卖顾客跨商家用餐需求是外卖企业已经得到了极大程度上的满足，“一单多商”已经成为新的消费场景。但存在很多问题，包括：
1.外卖配送成本居高不下
外卖行业发展历史短暂，发展基础不牢固，缺少在“一单多商”消费背景下的配送经验以及配送难度增大，致使外卖配送成本居高不下。一方面，在“一单多商”消费背景下，订单具有跨商家组合的特点，骑手在实际配送中，需要综合考虑出发时间、不同商家的出餐时间以及外卖顾客的要求时间，增大了配送难度，单单依据个人经验进行盲目配送很难达到最优配送，导致配送成本的升高。另一方面，由于缺少通过合理的订单分配方式来合理利用配送资源的经验，导致运力处于过高的水平，造成了车辆资源的浪费。过高的骑手资源成本是阻碍外卖平台盈利或扩大盈利的重要原因。
随着外卖规模的扩大，很多外卖企业已经意识到车辆调度的重要性，越来越多的企业希望通过合理的调度车辆实现规模效益，达到降本增效的效果。车辆调度包括订单分配以及车辆路径两个环节，订单分配影响着外卖车辆资源的占用，合理地分配订单，可以让外卖平台用更小的运力规模而完成更多的单量，有利于削减运力规模；车辆路径则影响着车辆资源的耗费情况，合理的安排车辆路径可以减少远距离的往复，有利于削减行驶成本。因此，科学合理地车辆调度可以有效降低配送车辆资源的投入、降低配送成本，对解决外卖配送成本居高不下的问题有着重要的意义。
2.传统外卖配送影响顾客用餐体验
在“一单多商”消费场景下，外卖顾客需求也发生了转变，呈现出了多样化、个性化组合跨商家点餐特点，外卖顾客对相应的外卖配送服务也提出更高的要求。“一单一取”(一个商家一次取餐)的传统配送，已经严重影响了外卖顾客的跨商家用餐体验。
一方面，由于缺少对跨商家订单的配送经验，致使一个订单需要过多骑手才能完成配送，导致外卖顾客取餐次数过多；另一方面，配送顺序的安排不合理，使得外卖顾客两次取餐时间间隔过长，严重地影响到顾客的跨商家用餐体验。因此，通过合理地安排车辆路径，减少取餐次数与取餐时间间隔，具有很高的现实意义。
各大外卖平台也已经意识到了外卖顾客的同地址不等待需求，美团推出智能点餐功能，可以提供适合不同数量、不同价位人群的用餐组合，订餐后一次取餐，但前提是在同一商家下单，不能跨商家；饿了么与大食代合作，在大食代下单，可以满足跨商家任意餐食搭配，一键通选，一笔配送费，同时送达，但前提是在大食代商场下单。可以看出，各大平台都开始在满足外卖顾客新需求上发力，虽然仍未见效果，但在“一单多商”的消费背景下，减少多次取餐等待时间以及取餐次数，已经成为提高顾客满意度的新的研究方向。
综上可知，当前城市外卖配送体量大，正面临着配送成本居高不下、用餐体验得不到高质量满足的双重考验。因此，外卖平台需要更合理的订单分配方式，整合发往同一地址订单，进而减少配送次数、削减运力规模；需要合理的配送路径，在满足订单要求的基础上，减少行驶配送成本、减少多次配送时间间隔。
外卖行业市场发展迅猛，但高速发展的同时也伴随着外卖配送安排不够合理、配送成本高、外卖顾客满意度不佳等大量问题涌现。因此一部分研究学者开始对外卖配送进行分析研究，但文献大都集中在提升用户满意度方面，缺乏直接对外卖资源配置优化方向的研究。
从订单特征、配送特征及时效约束性需求特征分别进行分析现有技术中存在的技术问题，具体如下：
一、针对“一单多商”的订单特征分析如下：
对于外卖平台来说，“一单多商”的订单形式对于提高顾客满意度有着战略意义。当前的“一单多商”具有订单中包含多个商家、订单可按商家进行拆分的特点。
(1)一个订单包含多个外卖商家
“一单多商”特指外卖订单中包含对多个外卖商家的订单，狭义的“一单多商”指的是同一外卖顾客通过购物车一键结算或者其他功能跨商家下单；广义则是，同一时间段内在同一收货地址下的所有外卖顾客跨商家下单。显而易见，在“一单多商”背景下，一个订单具有包含多个商家的特点。
(2)订单具有可拆分特性
由于配送难度大、配送运力限制等现实问题，当前的跨商家订单并不能一次送达外卖顾客手中，订单具有按商家可拆分的特性。如图1.1所示，(a)为传统的“一单一商”配送流程，(b)与(c)为“一单多商”订单配送流程，其中，(b)图代表订单拆分下的配送过程，(c)图代表订单不拆分形式下的配送过程。与传统的“一单一商”订单相比，“一单多商”订单在分配过程中，需要考虑订单是否具有可拆分性以及如何进行拆分。过多的拆分订单则意味着，订单配送过程中需要更多的外卖骑手参与，导致外卖配送中骑手成本的升高，同时，外卖顾客则需要过多次的取餐，影响了外卖顾客的用餐体验；而订单拆分次数过少，往往会造成骑手需要多次长距离往复进行取餐配餐，造成了外卖配送中行驶成本升高，同时也会增加外卖顾客的等待用餐时间，影响外卖顾客的用餐体验。因此，做好订单可拆分的外卖路径优化问题对于外卖企业具有重要的意义。
综上可知，在“一单多商”的消费场景下，订单具有包含多个商家、订单可拆分两个特征，在综合考虑成本和运力情况下，如何合理拆分订单已经成为了平衡外卖配送成本和顾客满意度的关键。
二、外卖配送需求特征分析如下：
为了研究外卖配送中外卖商家、外卖骑手以及外卖顾客的需求关系，以5个配送需求为例，其中包含了2个外卖顾客，4个外卖商家和一个骑手站点，具体需求情况如1.2图所示。
图1.2所表示的外卖配送需求情况可以做如下解释：1号外卖顾客对1号和2号外卖商家都有配送送餐需求，2号外卖顾客对2号、3号以及4号外卖商家都有配送送餐需求，四个外卖商家对骑手都有配送取餐需求，最终形成5个完整配送需求。
(1)配送取送餐需求具有对应关系
从图1.2可以看出，一个完整的配送需求包括配送取餐需求和配送送餐需求，所产生的配送取餐需求与配送送餐需求的数量具有一致性。同时，每个配送送餐需求都有一条配送取餐需求与之相对，配送送餐需求具有特殊性，与配送取送餐需求一一对应。
(2)配送需求需满足“先取后送”的要求
配送需求包括取餐需求和送餐需求，骑手在实际配送过程中，必须先后满足取餐和送餐需求，才能完成配送。同时，不同于传统由仓库对客户进行需求满足的配送过程，外卖配送过程不是一个独立的环节，而是需要外卖商家、外卖顾客以及骑手密切联系的过程。一个完整的配送过程，需要骑手先在骑手当前位置接受外卖订单，再根据取餐需求到相对应的外卖商家位置等待取餐，然后根据送餐需求到外卖顾客位置等待送餐，最后完成整个配送过程，订单所对应的外卖商家和外卖顾客必须先后被同一骑手访问。可以看出，配送需求具有“先取后送”的特点。
三、配送时间约束性特征分析
(1)时效性要求高
在外卖配送服务过程中，外卖顾客下单完成后往往与外卖平台约定好送达时间，如果外卖骑手晚于这个约定时间，将会造成顾客满意度的下降，影响了顾客体验，如果过多的顾客将此体验反馈到其他途径，将会很大程度的影响外卖企业的品牌。为了增强企业自身的竞争力，当前的外卖企业在外卖时效性上已经做了很多努力，各大平台深耕外卖时效，在覆盖三公里以内，保证30分钟上门，全程1小时送达；美团外卖推出准时达赔付，在不能满足时效性要求时进行赔付；饿了么、美团外卖入局无人机配送，计划打造未来五年覆盖5公里、时效10分钟的空中配送网络。由此可见，外卖配送的时效性要求将会越来越高。
(2)时间约束复杂
在“一单多商”实际配送过程中，为了满足外卖顾客对外卖的时效性要求，保证外卖在更快、更准确的时间送达外卖顾客手中，骑手不仅需要考虑外卖顾客对配送时间的约束性，还需要综合考虑骑手车辆最大行驶时间、不同外卖商家接受服务时间、不同外卖出餐时间等三个维度的时间约束，时间约束多，约束复杂。
外卖顾客对配送时间的约束是外卖顾客满意度评价标准之一，配送时间过长，将会影响外卖顾客的消费体验；其余三个时间约束，影响着骑手能否完成配送以及是否需要等待，可以说，时间约束是外卖配送能够顺利完成最为关键的考虑因素。因此，考虑外卖配送的时间约束是优化外卖路径的基础。
综上，外卖配送具有订单开拆分性、配送需求“先取后送”及时效性要求高等特征，为了更好的研究在“一单多商”消费背景下，外卖配送优化问题所具有的配送特点，本节从订单情况、配送情况、时间约束情况以及配送范围情况与传统外卖配送做了一个简单的对比，具体如下表1：
表1与传统配送的对比情况
综上可知，订单可拆分、订单包含多个配送需求以及时间约束更复杂的特点，使得本在较小范围进行配送的外卖配送路径优化问题变得异常复杂，单独靠人为经验进行安排路径几乎不可能在满足约束的条件下完成配送。
进一步分析城市外卖配送特征对车辆路径的影响如下：
传统的车辆路径问题(VRP)，指的是将所有客户的需求物资预先装车，车辆从仓库出发，在满足时间窗等约束下访问各客户，使行驶总距离或成本尽可能小，最后返回仓库的过程，并且每个客户只用接受一次服务。与传统的取送货车辆路径优化问题相比，外卖配送优化问题具有更复杂的约束，为了更好地进行车辆调度，以下从订单特征对车辆调度的影响、配送需求特征对车辆调度的影响以及时间约束性需求特征对车辆路径的影响三个部分进行深入地探究。
1)“一单多商”订单特征对车辆路径的影响
由于各种能力约束及其他约束的影响，有些订单并不能按照订单的要求完美的送达，这时就需要对订单进行合理的拆分，拆分过多将会影响顾客体验；拆分过少时，当前运力可能不能完成配送或者需要投入过高的费用进行配送。从车辆调度上来说，订单的可拆分，即订单需求可以分批完成。
外卖订单是否具有可拆分性，影响着骑手的配送路径。如图1.3所示，左侧是订单不可拆分情况下进行的配送，外卖顾客对1、2和3、4外卖商家的订单需求只能分别由一个骑手进行配送；右侧是订单可拆分情况下进行的配送，由于考虑订单可拆分，外卖顾客的订单需求可以由骑手分批完成，进而用更短的配送成本完成协同配送。在实际配送中，由于时间或载重等约束，使得“一单多商”订单并不能全都按图左侧路径进行配送，同时，过多的订单拆分也会导致客户满意度下降等问题。合理的分批送达，可以在满足订单需求的条件下，降低配送成本。
2)外卖配送需求特征对车辆路径的影响
外卖配送取送餐需求具有对应性以及“先取后送”的特征，外卖配送取送餐需求具有对应关系，则意味着骑手在计划访问一个配送需求中的外卖顾客时，也需要将此配送需求相对应的外卖商家安排在访问路径上，增加了车辆调度中的去收的数量。如图1.4所示，左侧为在不考虑配送需求具有对应关系的情况下进行配送，右侧为在考虑配送需求成对出现的情况下进行配送。可以看出，在加入配送需求成对出现的约束后，将会减少骑手访问的需求点，进而增加了骑手的使用量。
同时，配送需求“先取后送”影响了骑手的访问顺序，如图1.5所示，左侧为不考虑配送需求“先取后送”约束路线图，右侧为考虑此约束路线图。由于配送需求的先后顺序要求，骑手需要先到取餐需求位置进行取餐再到送餐需求的位置进行配餐，而左侧图的从2号外卖顾客到2号外卖商家的路线不能完成配送，使得骑手不得不改变访问顺序。可以看出，加入配送需求“先取后送”特征约束，影响了骑手的访问顺序。
3)时间约束性需求对车辆路径的影响
时效性是外卖顾客对于外卖配送好坏最直观的感受，时效性的高低直接影响了外卖配送的服务质量，是外卖企业不得不关注的一个重要特征。时效性特征即时间窗约束，影响着骑手配送的先后顺序。
如图1.6所示，左侧为按照最短路径进行配送的路线图，右侧则是考虑时间约束条件下的配送路线图，受到时间窗的影响，2号外卖商家不得不先于1号外卖商家进行配送，最后才能完成配送。可以看出，时间约束影响着骑手配送的访问顺序。
同时，时间窗也可能影响车辆不能完成此次配送，即需要另一辆车来帮助完成，如图1.7所示，左侧为不考虑时间窗的配送路线图，右侧为考虑时间窗的配送路线图，1号外卖商家和3号外卖商家时间窗冲突。由于外卖商家3的时间窗与外卖商家1的时间窗冲突，导致一个骑手不能完成本次配送任务，所以外卖顾客对3号外卖商家的需求需要通过其他骑手进行满足。可以看出时间窗对骑手的车辆路径有很大的影响，不仅会增加配送成本，同时也可能增加车辆。
综上，城市外卖配送优化问题中所涉及的订单可拆分、配送需求成对出现且“先取后送”以及时效性要求高等特征，都会影响车辆调度以及最终的车辆路径，这三个配送特征增加了城市外卖配送优化问题的模型构建及求解的难度。时间窗和配送需求成对出现且“先取后送”特征主要影响外卖配送的车辆路径，增加了车辆路径安排的难度；订单的可拆分性特征则是主要影响了车辆调度中的订单分配，如何在综合考虑配送成本及顾客满意度的情况下，将订单进行合理的拆分，需要更好更合理的车辆调度。
发明内容
本发明的目的是为了克服现有技术中的不足，提供一种基于一单多商情形下的城市电商外卖配送路径优化方法，针对在“一单多商”消费场景下，外卖企业所面临的配送问题，本发明根据当前“一单多商”的场景下的消费特性，提出了通过合理的车辆调度来降低配送成本、提高顾客满意度，并构建了城市外卖配送优化模型。这是对外卖配送问题新的尝试，也非常符合当前外卖企业降低配送成本、提高顾客满意度的需要。本发明的研究内容不仅在理论上完善了车辆路径以及外卖配送优化的理论体系，同时对外卖配送规划及配送车辆的调度起到重要的路径指导作用，具有一定的现实与理论意义。
本发明的目的是通过以下技术方案实现的：
一种基于一单多商情形下的城市电商外卖配送路径优化方法，一单多商指外卖顾客同时在不同商家下单的消费场景，包括：
S1.基于配送路径成本、发车成本、顾客满意度损失成本及若干约束条件构建外卖配送优化模型，目标函数为总成本最小；总成本为配送路径成本、发车成本、顾客满意度损失成本的和；
S2.设置参数，参数包括接受概率h、移除个数N、迭代次数Max_gen，及当前代数Gen；
S3.利用节约里程法产生初始解，并初始化选择不同移除算子与插入算子的概率，移除算子的选择概率为Pyi，插入算子的选择概率为Pci，设局部最优解为Xc，全局最优解为Xb，初始解为Xi，令Xi→Xc，Xi→Xb；
S4.通过ALNS算法不断地移除和不断地重新插入以改进初始解，当获得的新解得到改进或者满足接受解规则，下一次迭代中的初始解用当前的新解代替，最终完成迭代；具体如下：
S401.通过选择概率Pyi选择当前需要使用的移除算子Y移除N个需求点；
S402.通过选择概率Pci选择当前需要使用的重插入算子C将移除的N个需求点重新插入到序列中，得到局部最优解Xc；
S403.计算得到局部最优解值f(Xc)及最优值f(Xb),根据接受解规则更新当前最优解；
S404.根据ALNS算法的综合评分策略，评价算子组合，得到每个算子的选择概率，并进行更新；
S405.判断迭代过程中是否出现过此局部最优解，若是，则对算子组合进行减分，若否，则对算子组合进行加分；
S406.判断当前迭代次数是否大于最大允许迭代次数，若否，则更新迭代次数，Gen→Gen+1，重复S401-S406，若是，则迭代终止。
进一步的，步骤S1中，
(101)配送路径成本中配送路径长度是外卖配送员从当前位置出发完成所有订单取餐和送餐任务的配送路线长度，xijk是0-1变量，为1时代表骑手k从i点行驶到j点，否则为0；dij表示点i和点j之间的距离，c0代表单位距离配送费用；配送路径成本的数学表达式为：
(102)发车成本包括骑手半固定成本、辅助支持成本；
骑手半固定成本包括完成固定工资以及配套工具费用，配套工具费用包括工装费用、培训费用、车辆费用以及相关的设备费用。
辅助支持成本包括技术研发投入成本、系统支持成本、相关人员参与成本、广告营销成本；
用C1表示发车成本，为骑手半固定成本与辅助支持成本之和，发车成本的高低与骑手车辆数正相关，yk是决策变量，如果骑手k参与配送则为1，否则为0；其数学表达式为：
(103)顾客满意度损失成本
在当前订单能够拆分的配餐环境下，影响顾客满意度的因素包括：骑手对同一地址分批送的时间间隔和骑手对同一地址的配送次数；是决策变量，代表r订单包含j送餐需求，否则不包含；其中j∈Cn，r∈Dm；Fj表示订单j实际送达的时间，表示顾客对订单j期待送达的时间；顾客满意度损失成本的数学表达式为：
进一步的，其特征在于，外卖配送优化模型的目标函数为
约束条件有：
xijk＝0 or 1 (19)
其中，Vk表示骑手车辆集合，{1，2，3...,k}；Bn表示外卖取餐需求集合，{1，2，3...,n}；Cn表示外卖送餐需求集合，{n+1，n+1，n+3...,2n}；Dm表示订单集合，{1,2,3...，m}；c表示顾客满意度损失成本转化系数；Q0代表最大载重量；qi、qj为正代表送餐需求i、j所对应的需求量，为负代表取餐需求i、j所对应的供给量；Qi k、Qj k分别代表骑手k在i、j需求点的装载情况；分别表示i、j需求被骑手k完成服务时刻，其中i∈Bn，Cn，k∈Vk；Wij表示i需求与j需求被同一骑手先后满足时，i需求所对应的外卖商家的等待时间，其中i，j∈Bn，Cn；tk ij表示棋手k从位置i到位置j的所用时长，其中i,j∈Bn，Cn；Ei表示i需求所对应的外卖商家的最早接受服务时间，其中i∈Bn，Cn；Li表示i需求所对应的外卖商家的最晚接受服务时间，其中i∈Bn，Cn；M表示一个很大的常数；外卖商家也即顾客；
式(4)表示车辆总成本最小；其中，式(5)代表每个配送需求都要得到满足；式(6)代表每个骑手车辆如果离开配送中心，最终必须返回配送中心；式(7)和式(8)是骑手车辆能够闲置；式(9)代表流量守恒限制；式(10)和式(11)是外卖配送需求一一对应约束，并且外卖商家要在外卖顾客之前被访问；式(12)表示车辆访问必须满足需求点的时间窗限制；式(13)表示车辆到达时刻限制；式(14)和式(15)代表车辆各配送点装载约束；式(16)记录k骑手是否发车；式(17)记录车辆完成配送需求时刻；式(18)记录每个订单的最早被访问时间。
进一步的，步骤S3中，利用节约里程法产生初始解的过程如下：
首先选择适合车辆路径问题的整数编码方式，具体方式为：将外卖顾客的订单按商家进行拆分，形成N对配送需求，再将配送需求按照骑手满足顺序进行整数编码；解码过程与编码过程相反，根据需求对应关系找到相对应外卖顾客与外卖商家；
其次构造初始解，步骤如下：
(405)假设D为所有未分配车辆的外卖客户需求对集合；
(406)计算D中每个客户在满足时间窗以及载重约束下的最小插入成本与次小插入成本，找出次小插入成本与最小插入成本差值最大的客户对i，将其插入当前车辆，若当前没有客户能插入，则新安排一辆车，继续插入；
(407)将D集合中移除步骤(402)中找到的客户对i；
(408)如果D集合为空，则初始解构造完成，否则重复步骤(402)和(403)。
进一步的，所述移除算子包括：
(1)随机移除算子
随机移除算子指随机从已经分配好的路径中移除若干个客户，然后放入移除列表中，移除数量通过参数N控制，共将N对客户移除放入新的列表中；具体做法为，首先选择N个不同的送货点作为待移除对象，找到相对应得取货点，将这N对客户都移除并放入待插入列表中，完成移除过程；送货点对应外卖顾客，取货点对应外卖商家；
(2)最大距离移除算子
最大距离移除算子是将造成总距离增加最多的客户组合移除出来，每个客户组合的距离为移除前路径总距离与移除后的路径总距离之差；所移除的数量同样受参数N控制，重复移除N次，将移除的所有客户放入新集合中；
(3)路径移除算子
路径移除算子是随机拆散一条已经构建好的路径，将路径内所有客户添加到移除集合中；
(4)需求组合相似移除算子
需求相似移除算子是根据需求的相似性进行移除的算子，首先从当前解中随机移除一个需求客户组合，随后将在需求组合上与该客户组合需求量的大小相差最小的N-1个客户组合移除；最终移除的数量由参数N决定；需求相似移除算子是为找寻可替代或两两可交换位置的客户集合，通过需求相似移除客户点，能够加快算法的收敛；
(5)到达时间窗相似移除算子
时间窗相似移除算子指首先随机移除一个客户，然后将在车辆到达其他客户时间与到达该客户时间相差最小的N-1个客户进行移除；
(6)集中移除算子
集中移除算子是根据客户的位置，将外卖顾客按照距离进行聚类，然后随机移除一个集中区域的N个外卖顾客，同时移除外卖顾客所对应的外卖商家；移除的数量为N；集中移除算子需要预先设计集中区域。
进一步的，所述插入算子包括：
(1)贪婪插入算子
贪婪插入算子是指计算移除集合中每个客户插入所需要的代价，将代价最小的客户最先插入到部分解路径中，在移除集合中删除该客户，重新计算，直到移除集合为空；
(2)最大代价差插入算子
最大代价差插入算子是指计算移除集合中每个客户插入所需要的最小代价与次小代价，将代价差最大的客户插入到路径中，在移除集合中删除该客户，重新计算，直到移除集合为空。
进一步的，步骤S404中，基于现实配送特点，设计了综合评分法为每个算子计算分数，并加入挥发机制，历史分数占比会越来越小，具体设计如下：
(1)算子选择
使用若干种移除算子和插入算子混合进行算法优化，每次迭代根据分数情况来选择使用何种移除算子和插入算子；其中，分数越高，算子被选择出来的概率越大，首先根据分数选择使用何种移除算子进行移除，然后选择使用何种插入算子进行重插入操作；
(2)综合评分法
算子的选择概率是通过算子的评分确定的，算子的评分越高越容易被选择；通过C1、C2、C3既代表评分加成也代表评分等级，fn(C)代表下一次迭代中算子C的评分情况，fn(总)代表下一次迭代与C算子类型一样的所有移除算子或插入算子的最终评分之和，其中C1>C2>C3，n指第n代；具体解释为：当新得到的新解比历史最优解更好时，当前所使用的移除算子和重插入算子的分数增加C1；当新解不优于历史最优解但优于当前解时，当前所使用的移除算子和重插入算子分数增加C2；当新解不优于历史最优解也不优于当前解时，但历史迭代未出现过，则当前所使用的移除算子和重插入算子分数增加C3，其他情况不加分；
(3)挥发机制
挥发机制指的是每次迭代后，所有算子的分数需要乘以百分数h，0<h<1。
本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现所述基于一单多商情形下的城市电商外卖配送路径优化方法的步骤。
本发明还提供一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现所述基于一单多商情形下的城市电商外卖配送路径优化方法的步骤。
与现有技术相比，本发明的技术方案所带来的有益效果是：
1.本发明根据在当前消费背景下城市外卖配送成本居高不下、顾客在取餐端满意度不高的问题，从平台的角度进行优化研究，分析了订单分配和路径规划的影响因素，并构建了带时间窗的订单可拆分的外卖配送优化模型，丰富了车辆路径的理论模型。
2.针对订单可拆分带时间窗的外卖配送模型的复杂程度，选择了适合求解复杂问题的大规模搜索算法，并根据外卖配送对求解时效的要求，设计了集中移除算子，并引入快速评分策略来改善自适应大规模搜索算法性能。丰富了外卖配送车辆路径优化研究，也为求解复杂问题、同时对时效要求高的模型提供了算法参考。
3.本发明为解决当前外卖配送成本居高不下、外卖顾客用餐满意度不高的双重问题，结合外卖配送的相关特征，进行了理论建模，得到了相应的解决方案，并能够根据现实情况的不同而进行动态的调整。该解决方案对降低配送成本、提高顾客满意度都具有一定的现实参考意义。
而元启发式中，禁忌搜索在求解复杂问题的表现不如大规模搜索算法，因此，本发明选择了自适应大规模搜索算法对模型进行求解。
基于此，本发明从平台角度出发，以配送成本最低与顾客满意度最大为目标，结合“一单多商”的配送特点，构建了带时间窗的订单可拆分的取送货路径优化模型，并经过算法综述，对算法进行选择，最终利用自适应的大规模搜索算法。
附图说明
图1.1是订单配送流程图。
图1.2是骑手配送需求情况示意图。
图1.3是订单可拆分的配送路径图。
图1.4是配送需求成对对比图。
图1.5是配送需求“先取后送”车辆配送路线图。
图1.6是带时间窗的配送路线图。
图1.7是带时间窗的配送路线图。
图2是外卖配送路线图。
图3是改进的自适应大规模搜索算法框架图。
图4是编码过程示意图。
图5是最大距离移除示意图。
图6是路径移除示意图。
图7是需求相似移除过程示意图。
图8是到达时间相似移除过程示意图。
图9是集中移除过程示意图。
图10是贪婪插入部分过程示意图。
图11是最大代价插入算子部分过程示意图。
图12是外卖商家及用户分布图。
图13是城市外卖配送路线示意图。
具体实施方式
以下结合附图和具体实施例对本发明作进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
实施例1
本发明所研究的外卖配送模型求解问题可以概述为：某外卖平台承载了一定区域的外卖配送任务，该区域某时段共有1个配送站点，站点内骑手数量无限制，m份外卖订单，订单可按商家进行拆分为n份子订单(配送需求)。在配送过程中，为了完成每个子订单，骑手必须在满足时间约束条件下，先到相应的外卖商家取餐，再到相应的外卖顾客配餐，在完成所分配的所有子订单的配送任务后返回配送站点，完成配送。其中，配送成本受骑手数量和骑手行驶总距离影响，顾客满意度受外卖顾客取餐次数以及多次取餐的时间间隔影响。
本发明要解决如何将n对配送需求(子订单)分配给合适的外卖骑手进行配送，得到配送成本小和顾客满意度高的配送方案，该问题的可视化方案如图2所示。
1.问题假设
外卖配送具有“先取后送”的特征，可以归纳为取送货问题。在此模型中，将配送站点作为取送货问题中的配送中心，外卖商家为取货点，外卖顾客为送货点，骑手通过不断地取货、送货，最终返回站点作为一条完整的路径，具体假设如下：
(1)骑手在完成所有任务后需要回到出发地；
(2)骑手先从外卖商家取餐再向外卖客户配送；
(3)外卖顾客可以接受不同骑手进行配送服务；
(4)外卖骑手的配送速度已知；
(5)外卖商家、骑手、外卖顾客的信息已知，在外卖平台收到订单请求后即可获得；
(6)距离信息已知，可通过坐标位置计算得到；
(7)骑手车型固定，负载量已知，在配送的过程中，客户需求量之和不能超过最大载重量。
(8)外卖消费者和外卖商家有期望接收服务时间窗口；
(9)骑手同时完成订单内多个配送需求时，按一次服务时间计算；
2.参数说明
(3)决策变量描述
Xijz:0-1变量，Xijz为1时，代表骑手z从i点行驶到j点，否则为0。
2.1.目标函数说明
本实施例从平台的角度出发，结合外卖配送特点，综合考虑了外卖配送过程中的配送行驶路线长度、骑手发车成本以及顾客满意度三个因素，对这三个因素的分析如下：
(1)配送路径成本
配送路径长度是外卖配送员从当前位置出发完成所有订单取餐和送餐任务的配送路线长度。配送路径长度影响外卖配送平台中订单的平均配送时间，进而影响众包外卖配送平台的配送效率，同时配送路径长度还影响外卖配送员的配送成本。从平台的角度出发，优化配送路线长度一方面是为了提高平台的配送效率，另一方面也是为了降低配送员的配送成本，保证为配送员提供良好的路线规划服务体验。xijk是0-1变量，为1时代表骑手k从i点行驶到j点，否则为0。dij表示点i和点j之间的距离，c0代表单位距离配送费用。数学表达式为：
(2)发车成本
外卖配送成本居高不下，一直是困扰外卖平台盈利或扩大盈利的问题，为了更清晰了解配送成本流向，找到降低配送成本的关键，分析配送成本组成成份的具体情况是必不可少的。外卖配送发车成本主要包括骑手半固定成本、辅助支持成本，具体情况如下：
骑手半固定成本：包括完成固定工资以及配套工具费用，配套工具费用包括工装费用、培训费用、车辆费用以及相关的设备费用等。
辅助支持成本：包括技术研发投入成本、系统支持成本、相关人员参与成本、广告营销成本等。
为了方便表示，本实施例用C1表示发车成本，为骑手半固定成本与辅助支持成本之和，发车成本的高低与骑手车辆数正相关，yk是决策变量，如果骑手k参与配送则为1，否则为0。其数学表达式为：
(3)顾客满意度损失成本
在当前订单能够拆分的配餐环境下，影响顾客满意度的因素包括：骑手对同一地址分批送的时间间隔和骑手对同一地址的配送次数；是决策变量，代表r订单包含j送餐需求，否则不包含。其中j∈Cn，r∈Dm；Fj表示订单j实际送达的时间，表示顾客对订单j期待送达的时间。顾客满意度损失成本的数学表达式为：
3.构建外卖配送优化模型
根据上述的模型参数和平台考虑的配送路线长度、车辆成本、以及同一地址收获间隔三个因素，再结合外卖配送过程中的外卖订单成对约束、一次性最大接单量约束等等，本实施例外卖配送优化模型的数学表达式如下:
目标函数：
约束条件：
xijk＝0 or 1 (19)
其中，Vk表示骑手车辆集合，{1，2，3...,k}；Bn表示外卖取餐需求集合，{1，2，3...,n}；Cn表示外卖送餐需求集合，{n+1，n+1，n+3...,2n}；Dm表示订单集合，{1,2,3...，m}；c表示顾客满意度损失成本转化系数；Q0代表最大载重量；qi、qj为正代表送餐需求i、j所对应的需求量，为负代表取餐需求i、j所对应的供给量；Qi k、Qj k分别代表骑手k在i、j需求点的装载情况；分别表示i、j需求被骑手k完成服务时刻，其中i∈Bn，Cn，k∈Vk；Wij表示i需求与j需求被同一骑手先后满足时，i需求所对应的外卖商家的等待时间，其中i，j∈Bn，Cn；tk ij表示棋手k从位置i到位置j的所用时长，其中i,j∈Bn，Cn；Ei表示i需求所对应的外卖商家的最早接受服务时间，其中i∈Bn，Cn；Li表示i需求所对应的外卖商家的最晚接受服务时间，其中i∈Bn，Cn；M表示一个很大的常数；外卖商家也即顾客；
外卖配送优化模型的式(4)表示车辆总成本与顾客满意度损失成本最小。其中，式(5)代表每个配送需求都要得到满足；式(6)代表每个骑手车辆如果离开配送中心，最终必须返回配送中心；式(7)和式(8)是骑手车辆可以闲置；式(9)代表流量守恒限制；式(10)和式(11)是外卖配送需求一一对应约束，并且外卖商家要在外卖顾客之前被访问。式(12)车辆访问必须满足需求点的时间窗限制；式(13)车辆到达时刻限制；式(14)和式(15)代表车辆各配送点装载约束；式(16)记录k骑手是否发车；式(17)记录车辆完成配送需求时刻；式(18)记录每个订单的最早被访问时间。
城市外卖配送问题具有订单可拆分、需求成对出现等特征，比经典的车辆路径问题更为复杂。由于需要考虑到配送的时效性、配送成本以及对同一地址配送时间间隔三个因素，所以，一方面需要配送中心能够得到高质量的解，另一方面也需要配送中心能够快速响应订单需求。因此，本实施例选用了适合求解复杂问题的自适应大规模搜索算法。本实施例在介绍了算法思想、算法框架、移除算子和插入算子以后，提出了结合城市外卖配送特点，对该算法的初始解、算子设计、接受解规则所作的改进。最后，选用和取送货问题的标准测试算例进行测试，验证了该改进算法的有效性。
自适应大规模搜索算法(Adaptive Large Neighborhood Search heuristic，ALNS)是在大规模搜索算法(Large Neighborhood Search heuristic,LNS)的基础上改进得到，由于算法实现容易、原理简单、算法性能好的特点，自Shaw等(1998)首次提出之后，已经得到了广泛的应用，在求解复杂问题上，具有很好的优势。
自适应大规模搜索算法的核心思想是通过不断地移除(移除算子)和不断地重新插入(插入算子)来改进初始解，当获得的新解得到改进或者满足接受解规则，那么在下一次迭代中初始解用当前的新解代替。不同于大规模搜索算法只有一个移除算子和一个插入算子，自适应大规模搜索算法采用多个移除算子和多个插入算子，根据历史的求解质量情况动态地对算子进行打分，每次迭代中根据不同算子的分数，动态地选择使用哪个移除算子以及哪个重插入算子。
为有效地求解本实施例所提模型，本实施例对算法进行了一定地改进，具体框架如图3所示，具体求解步骤为：
S1：设置参数，需要设置的参数包括接受概率h、移除个数N、迭代次数Max_gen，及当前代数Gen；
S2：初始化，首先需要利用节约里程法产生初始解，并且需要初始化选择不同移除算子与插入算子的概率，移除算子的选择概率为Pyi，插入算子的选择概率为Pci，设当前最优解为Xc，最优解为Xb,初始解为Xi,令Xi→Xc,Xi→Xb；
S3：迭代过程：
S301:通过概率Pyi选择当前需要使用的移除算子Y移除N个需求点；
S302:通过概率Pci选择当前需要使用的重插入算子C将移除的N个需求点重新插入到序列中，得到新解Xc；
S303:计算得到新解值f(Xc)及最优值f(Xb),根据接受解规则更新当前最优解；
S304:根据算法的综合评分策略，评价算子组合，得到每个算子的选择概率，并进行更新；
S305:判断迭代过程中是否出现过此新解，若是，则对算子组合进行减分，若否，则对算子组合进行加分；
S306:判断当前迭代次数是否大于最大允许迭代次数，若否，则更新迭代次数，Gen→Gen+1，重复S301-S306，若是，则迭代终止。
具体的，步骤S2中，
算法编码是城市外卖配送问题的解空间转换成算法能够处理的解空间的一种方式。算法编码是算法设计中需要解决的第一步，同样也是关键一步，不同的编码方式对于求解速度以及求解质量都有一定的影响。
由于外卖配送路径为离散排列，故本实施例选择了适合车辆路径问题的整数编码方式，具体方式为：将外卖顾客的订单按商家进行拆分，形成N对配送需求，再将配送需求按照骑手满足顺序进行整数编码。以一个区域共有2份订单，3个外卖商家，2个外卖顾客，共形成4对(8个)配送需求为例，具体信息及编码情况如图4所示。其中编码的数字意义为：0代表配送站点，1-4为取餐需求编号，5-8为送餐需求编号，排列的先后代表需求满足的先后顺序。
解码过程与编码过程相反，需要根据需求对应关系找到相对应外卖顾客与外卖商家，图4解码为：站点-B1-B2-C1-C1-B2-B3-C2-C2-站点。
初始解构造：不同于种群算法，自适应大规模搜索算法的初始解只需要一个，从一个初始解进行迭代优化，因此好的初始解有利于优化算法的收敛速度。为了得到较好的初始解，本实施例借鉴了Clarke等(1964)提出的节约法,具体构造方法如下：
(1)假设D为所有未分配车辆的外卖客户需求对集合；
(2)计算D中每个客户在满足时间窗以及载重约束下的最小插入成本与次小插入成本，找出次小插入成本与最小插入成本差值最大的客户对i，将其插入当前车辆，若当前没有客户能插入，则新安排一辆车，继续插入；
(3)将D集合中移除(2)中找到的客户对i；
(4)如果D集合为空，则初始解构造完成，否则重复(2)和(3)步骤。
具体的，步骤S2中移除算子具体如下：
移除算子是自适应大规模搜索算法最为重要的两个算子之一，影响着算法的全局探索能力与局部搜索能力，可以说是算法可以优化的关键。对不同过程采用不同的移除算子可以有效地改进算法，本实施例所用到的移除算子有六个，其中集中移除算子是结合当前外卖场景中外卖顾客集中的特性所提出来的改进算子，具体如下：
(1)随机移除算子
随机移除算子即随机从已经分配好的路径中移除个客户，然后放入移除列表中，移除数量通过参数N控制，共将N对客户移除放入新的列表中。具体做法为，首先选择N个不同的送货点(外卖顾客)作为待移除对象,找到相对应得取货点(外卖商家),将这N对客户都移除并放入待插入列表中，完成移除过程。该算子由于随机的特性，增加了解决方案的多样性，可以有效地提高算法的全局搜索能力。
(2)最大距离移除算子
最大距离移除算子即是将造成总距离增加最多的客户组合移除出来，每个客户组合的距离为移除前路径总距离与移除后的路径总距离之差，如图5所示，左侧为移除前的路径，右侧为移除客户组合1之后的路径，客户组合1的移除距离为两条路径长度之差。依次计算剩余客户组合的移除距离，按从大到下的规则排序，选择拥有最大移除距离的客户进行移除(右侧)。所移除的数量同样受参数N控制，重复移除N次，将移除的所有客户放入新集合中。
(3)路径移除算子
路径移除算子即是随机拆散一条已经构建好的路径，将路径内所有客户添加到移除集合中。如图6所示，左侧为初始车辆路径，通过路径移除算子，选择了R2这条路径进行移除，右侧为移除后的路径。
(4)需求组合相似移除算子
需求相似移除算子是根据需求的相似性进行移除的算子，首先从当前解中随机移除一个需求客户组合，随后将在需求组合上与该客户组合比较相似的N-1个客户组合移除。如图7所示，假设顾客1的需求为25，顾客2的需求为30，顾客3的需求量为15，顾客4、5的需求分别为10、40，在算子刚开始先移除客户组合1的情况下，由于顾客1的需求量与顾客3的需求量相似，故客户组合3也会被移除，最终移除的数量由参数N决定。该算子主要目的为找寻可替代或两两可交换位置的客户集合，通过需求相似移除客户点，也可以加快算法的收敛。
(5)到达时间窗相似移除算子
时间窗相似移除算子，与需求相似移除算子类似，首先随机移除一个客户，然后将在车辆到达时间与该客户相似的N-1个客户进行移除。如图8所示，客户组合1与3的到达时间接近，所以在首先移除客户组合1的情况下，客户组合3也会被移除。该算子和需求移除算子功能类似，是需求移除算子的补充，同样可以加快算法的收敛。
(6)集中移除算子
与算法基础设计中的移除算子不同，集中移除算子是本实施例根据当前外卖顾客分布集中这一特点所提出的一种新算子。外卖顾客分布集中，则意味着在实际配送中，车辆在同地址位置容易出现交叉，同地址外卖顾客容易被整合。
具体做法是根据客户的位置，将外卖顾客按照距离进行聚类，然后随机移除一个集中区域的N个外卖顾客，同时移除外卖顾客所对应的外卖商家。如图9所示，外卖顾客2与外卖顾客3属于A区域，左侧为初始路径，右侧为在A区域移除客户组合2与客户组合3之后得到的部分解，区域A中每个客户被移除的概率相等，移除的数量跟参数N的设置有关。集中移除算子需要预先设计集中区域，是一种更小范围的随机移除算子。
具体的，步骤S2中插入算子具体如下：
插入算子同样也是自适应大规模搜索算法两个最重要的算子之一，主要功能是将移除的客户集合按照一定的规则重新插入到路径内，重新插入的方式不同，将会直接影响解的质量。本实施例所用插入算子有两个，具体如下：
(1)贪婪插入算子
贪婪插入算子的具体设计为：计算移除集合中每个客户插入所需要的代价，将代价最小的客户最先插入到部分解路径中，在移除集合中删除该客户，重新计算，直到移除集合为空。以图10为例，首先获得移除算子处理后的部分解以及待插入集合，计算待插入集合的每个客户在部分解中每个插入位置的成本，经过比较选择具有最小插入成本的客户为5，最小插入位置为5与3之间，将集合中的5插入到部分解的6-3之间，形成新的部分解和待插入集合，重复以上步骤，直到待插入集合为空集。
(2)最大代价差插入算子
最大代价差插入算子的具体设计为：计算移除集合中每个客户插入所需要的最小代价与次小代价，将代价差最大的客户插入到路径中，在移除集合中删除该客户，重新计算，直到移除集合为空。以图11为例，在获得部分解与待插入集合后，首先计算待插入集合客户在部分解所有位置的插入成本，然后对于每个客户，计算其次小与最小插入成本的差值，差值最小的客户为此次插入的客户，其最小成本插入位置为其插入位置，进行插入，形成新的部分解以及待插入集合，重复以上，指导待插入集合为空集。
此外，接受解的规则影响着算法解的多样性及解优化的方向，为了保证算法解的多样性，本实施例使用以概率接受新解。具体操作为：当新解优于当前解，则接受新解；当新解不优于当前解，则依照概率f,接受新解,其中0<f<1。概率f和当前迭代次数无关，与新解和当前解的差值有关，具体设置需要经过算例测试确定。
具体的，步骤S304中的设计有算法优化策略：
由于外卖在实际配送中不仅需要合理的配送路径，同时也需要快速地响应订单，即外卖配送对求解质量与求解速度都有要求。因此，本实施例结合当下现实中外卖配送的特点，对自适应大规模搜索算法做了相应的改进，通过将模拟退火框架改为同样概率接受差解、增加集中移除算子两种方式来提高算法收敛性，加快求解速度；通过设计综合评分法为算子性能打分来提高算法求解质量，本节介绍算法所采用的改进策略。
由于算法在运行的不同阶段中，不同算子发挥的作用不同，因此需要动态调整每次选择每个算子的概率，自适应调节机制就是通过自适应的方法调节每个算子的被选择概率的一种方式。本实施例基于现实配送特点，设计了综合评价打分法为每个算子计算分数，并加入挥发机制，历史分数占比会越来越小，具体设计如下：
(1)算子选择
为了避免使用一种算子而使算法求解过早陷入局部最优，本实施例使用了多种移除和插入算子混合进行算法优化，每次迭代根据分数情况来选择使用何种移除算子和插入算子。其中，分数越高，算子被选择出来的概率越大，首先根据分数选择使用何种移除算子进行移除，然后选择使用何种插入算子进行重插入操作。
(2)综合评分法
算子的选择概率是通过算子的评分来确定的，算子的评分越高越容易被选择。如表2所示，其中C1、C2、C3既代表评分加成也代表评分等级，fn(C)代表下一次迭代(第n代)中算子C的评分情况，fn(总)代表下一次迭代(第n代)与C算子类型一样的所有移除算子或插入算子的最终评分之和，其中C1>C2>C3。具体解释为：当新得到的新解比历史最优解更好时，当前所使用的移除算子和重插入算子的分数增加C1；当新解不优于历史最优解但优于当前解时，当前所使用的移除算子和重插入算子分数增加C2；当新解不优于历史最优解也不优于当前解时，但历史迭代未出现过，则当前所使用的移除算子和重插入算子分数增加C3，其他情况不加分。
表2算子C综合评分情况表
(3)挥发机制
挥发机制是类似于蚁群算法中的信息素挥发，每次迭代都有一定程度的削减历史的求解效果对当前算子选择概率的影响，对拓展解的多样性，提高算法求解效果，有显著效果。调节机制下的挥发机制指的是，每次迭代后，所有算子的分数需要乘以百分数h，0<h<1。
为了验证自适应大规模搜索算法在解决外卖配送问题上的有效性，本实施例对算法的有效性进行了测试。本实施例针对当前并没有文献对需求可拆分的多目标取送货问题展开研究，选择了与模型相近的带时间窗的取送货问题标准的56个测试集，与当前已经公布的最优解与最短求解时间进行比较分析，并对结果进行分析，最终验证了算法的有效性。
为了方便测试本实施例所使用的算法是否能够有效的解决城市外卖配送问题，本实施例选用了PDPTW的Benchmark算例和已经公布的最优解，算例来自http:// www.sintef.no/projectweb/TOP/Problems/PDPTW，并结合传统大规模搜索算法进行测试评价。算例共包含3类，即Lc、Lr以及Lrc类，其中算例Lc类中客户位置是聚类分布,算例Lr类中客户位置随机分布，算例Lrc类中客户位置随机及聚类混合分布，共56个测试集，每个测试集都包含100个需求点。这些基准数据和最优解均下载得到。
考虑到外卖配送问题与标准的取送货问题有所不同，本实施例对标准测试集进行了一定的改进，测试问题可以描述为：现有某外卖平台，通过同样的车辆对不同外卖商家和外卖顾客提供取餐和配餐服务，外卖商家和外卖顾客的位置是在边长为10公里的矩形内部随机产生，同一外卖顾客可能对多个不同外卖商家有需求。为此，为了以标准取送货测试集来测试该问题求解的算法，在测试集数据的基础上另外随机插入5份跨商家订单，每份订单包含一个外卖顾客和五个外卖商家。
考虑到标准取送货测试集中需求点在以边长为100千米的矩形内产生，配送成本为1元/km，但缺少发车成本以及顾客满意度转化成本。因此，为了方便求解，根据外卖实际情况中的配送电车的行驶配送成本及发车成本进行了折算，最终行驶成本设为1元/m，发车成本设为20元/辆，将顾客满意度损失成本转化系数c设为常数1。
1.算法参数设置
本实施例所使用的ALNS算法总共包含14个参数，通过大量的实验，找到了效果比较好的参数数值，具体如下：
i)移除客户需求数量N＝20；
ii)选择评分，优于历史最优值得C1＝33；
iii)优于当前解的C2＝9；
iv)劣于当前解，但最终解被接受C3＝13；
v)分数衰减权重h＝0.5；
vi)最大迭代次数max_gen＝500；
2.结果对比分析
本实施例主要从算法求解质量以及算法求解速度两个方面对算法的有效性进行测试，算法对每个测试集进行运行求解10次，每次迭代500代，结果保留两位小数，取十次运行的平均最优解与平均运行时间与传统的大规模搜索算法求解结果进行比较。其中，改进的ALNS在44个测试集中得到的结果不劣于传统的大规模搜索算法，两者每个测试集的GAP值(最优解的差距)最大不超过7.51％，平均求解时间分布较为均匀，受不同测试集影响更小，求得最优解用总平均用时是传统大规模搜索算法的三分之一，具体结果表3所示：
表3取送货数据集测试结果表
表3取送货数据集测试结果表(续)
注：GAP％表示本实施例改进的ALNS相对于传统的大规模搜索算法优化百分比
(1)算法求解效果对比
从求解效果上来看，自适应大规模搜索算法在56个测试集中，共有44个能够得到最优解，与传统大规模搜索算法所使用算法相比，改进的自适应大规模搜素算法能够得到同样或者更好的解，在求解质量上具有明显的优势。
从求解三类类测试集来看，自适应大规模搜索算法在Lc类聚类测试集优化结果尤其好，符合对算法设计优化目标与预期(外卖配送中，外卖顾客与外卖商家分布集中)。算法适合求解聚集性取送货问题，在求解质量上具有一定的有效性。
从求解速度上来看，自适应大规模搜素算法在求解56个测试集中，平均求解时间分布较为均匀，受不同测试集影响更小，求得最优解用总平均用时是传统大规模搜索算法的三分之一，可以验证算法在求解速度上具有一定的优势。
(2)不同规模对算法影响分析
为了更好地研究客户规模对成本、送达间隔、送达次数的影响，本实施例选取了客户规模分别为100、200、400的分布集中的lc106、lc206、lc406测试集，主要研究本实施例的模型在不同规模客户上的表现情况。根据本实施例的模型，具体情况如表4所示：
表4不同客户规模结果表
由表4可观察到，客户规模越大成本越高、配送时差越小、配送次数越小，客户规模对其三者都有一定的影响。深入分析发现，成本所降低比列高于规模扩大比例，客户规模对三者都具有规模效益，算法求解效果符合预期。
综上，算法在测试集中测试结果符合现实预期，具有一定的有效性。同时，相比于传统大规模搜索算法，本实施例所使用的自适应大规模搜索算法在求解取送货问题上无论在求解质量或是求解速度上，都具有一定的有效性，对不同规模的算例也具有一定的适用性，并且对集中分布的算例表现更好，适合求解该问题。
实施例2
本实施例首先对M公司的背景及配送模式进行介绍，然后通过调研市场数据设置相应的配送位置分布、时间窗、需求量、需求配对情况、服务时间等数据。最后通过模型化问题并进行求解，为M公司的发展提供了结果分析，同时验证了算法的实用性。
本实施例以M公司的城市外卖配送为例，对其在天津市南开区的配送数据为对象进行研究。M公司是负责外卖配送调度的一家公司，国内业务规模大、已经成为我国外卖配送行业的两大实力公司之一。外卖行业是一个进入门槛较低的行业，为了更好的抢夺市场，外卖公司大都以降低配送成本和提高顾客满意度的方式来提高竞争力。
M公司意识到了外卖配送的特殊性(短距离配送)，为了降低配送成本，已经决定将车辆资源(车辆成本)和车辆行驶配送成本作为总成本进行优化；同时，意识到同一地址客户服务质量尚有优化空间，决定提高同一地址收货体验。如图12所示，M公司地一个外卖配送站点位于南开区，负责满足附近区域内的订单需求，其中，该区域共有10个商家，图中用B1-B10，共有20个外卖顾客，图中用C1-C20表示。具体分布情况如图12。
一、相关数据集信息
本实施例以M公司作为研究对象，收集外卖市场相关信息，主要包含车辆信息、外卖商家相关数据以及外卖顾客相关数据，具体包括地理位置信息、订单需求信息、配对需求信息、时间窗信息。
1.车辆信息
M公司在南开区只有一个发车中心，发车中心中每个车辆的具体信息如表5所示：
表5车辆信息表
2.位置及时间窗相关信息
为了表示方便，本实施例在整理出每个客户位置的经纬度后，对其经纬度进行了横纵坐标的转化，具体整理数据如表6所示。
表6外卖位置及时间窗信息表
3.订单信息
外卖顾客对各个商家有不同的需求，具体如表7所示：
表7订单需求表
4.配送配对需求信息
具体外卖商家与外卖顾客配对情况如表8所示：
表8外卖运输配对情况信息表
表8外卖运输配对情况信息表(续)
二、本实施例求解结果分析
为了验证算法和模型得有效性，本实施例利用外卖公司实际案例来进行测试。本实施例所使用的大规模搜索算法是用Matlab实现，最大迭代次数为200，具体参数如上章所述。
根据M外卖公司的车辆信息、订单信息以及地理位置信息等，本实施例用改进的自适应大规模搜索算法求解该问题，最终优化结果按照具体如表9所示：
表9外卖配送路径情况表
表9中C1-C20代表外卖顾客，B1-B10代表外卖商家，D代表发车中心,路径中C18-C18代表同一时间满足了外卖顾客18的配送需求。
从图13可以看到，外卖配送路径中每个位置都是很多路径的交点，原因在于在当前配送环境中，外卖顾客和外卖商家允许多次访问。同时，车辆路径有很多交叉的情况，这是因为本实施例的优化目标不再是传统的只考虑降低行驶配送成本，同时还考虑了发车成本情况，与行驶耗费成本相比，车辆资源成本更高，减少发车成本对于降低总成本具有更明显的效果。
为了验证基于“一单多商”的外卖配送优化方式的有效性，本实施例就优化结果中的行驶配送成本、发车成本、同订单配送次数以及同订单配送时间间隔与传统外卖配送优化方式进行对比，其中，传统的外卖配送是一种通过降低行驶配送成本进行降本增效的方式。由于本实施例所用案例规模较小，为了使结果更直观，所以具体结果以单平均作为比较，结果保留3位小数，具体比较结果如表10所示。
表10与传统方式比较结果
从表10可以看出，基于“一单多商”的外卖配送优化方式虽然在行驶配送成本上表现不如传统外卖配送方式，但由于成功削减了发车成本，在总成本上仍然优于传统方式；同时，在与同地址顾客满意度相关的配送次数与配送相隔时长都优于传统外卖配送方式。因此，与传统外卖优化配送方式相比(以降低行驶配送成本为目标)，本发明提供的基于“一单多商”的外卖配送优化方式具有更好的实用性，可以帮助企业提高顾客满意度、降低配送成本，进而提高竞争力。
优选地，本申请的实施例还提供能够实现上述实施例中的基于一单多商情形下的城市电商外卖配送路径优化方法中全部步骤的一种电子设备的具体实施方式，电子设备具体包括如下内容：
处理器(processor)、存储器(memory)、通信接口(Communications Interface)和总线；
其中，处理器、存储器、通信接口通过总线完成相互间的通信；通信接口用于实现服务器端设备、计量设备以及用户端设备等相关设备之间的信息传输。
处理器用于调用存储器中的计算机程序，处理器执行计算机程序时实现上述实施例中的基于一单多商情形下的城市电商外卖配送路径优化方法中的全部步骤。
本申请的实施例还提供能够实现上述实施例中的基于一单多商情形下的城市电商外卖配送路径优化方法中全部步骤的一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，该计算机程序被处理器执行时实现上述实施例中的基于一单多商情形下的城市电商外卖配送路径优化方法的全部步骤。
上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。
虽然本申请提供了如实施例或流程图的方法操作步骤，但基于常规或者无创造性的劳动可以包括更多或者更少的操作步骤。实施例中列举的步骤顺序仅仅为众多步骤执行顺序中的一种方式，不代表唯一的执行顺序。在实际中的装置或客户端产品执行时，可以按照实施例或者附图所示的方法顺序执行或者并行执行(例如并行处理器或者多线程处理的环境)。
本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
本发明并不限于上文描述的实施方式。以上对具体实施方式的描述旨在描述和说明本发明的技术方案，上述的具体实施方式仅仅是示意性的，并不是限制性的。在不脱离本发明宗旨和权利要求所保护的范围情况下，本领域的普通技术人员在本发明的启示下还可做出很多形式的具体变换，这些均属于本发明的保护范围之内。

Claims (9)

1.一种基于一单多商情形下的城市电商外卖配送路径优化方法，一单多商指外卖顾客同时在不同商家下单的消费场景，其特征在于，包括：
S1.基于配送路径成本、发车成本、顾客满意度损失成本及若干约束条件构建外卖配送优化模型，目标函数为总成本最小；总成本为配送路径成本、发车成本、顾客满意度损失成本的和；
S2.设置参数，参数包括接受概率h、移除个数N、迭代次数Max_gen，及当前代数Gen；
S3.利用节约里程法产生初始解，并初始化选择不同移除算子与插入算子的概率，移除算子的选择概率为Pyi，插入算子的选择概率为Pci，设局部最优解为Xc，全局最优解为Xb，初始解为Xi，令Xi→Xc，Xi→Xb；
S4.通过ALNS算法不断地移除和不断地重新插入以改进初始解，当获得的新解得到改进或者满足接受解规则，下一次迭代中的初始解用当前的新解代替，最终完成迭代；具体如下：
S401.通过选择概率Pyi选择当前需要使用的移除算子Y移除N个需求点；
S402.通过选择概率Pci选择当前需要使用的重插入算子C将移除的N个需求点重新插入到序列中，得到局部最优解Xc；
S403.计算得到局部最优解值f(Xc)及最优值f(Xb),根据接受解规则更新当前最优解；
S404.根据ALNS算法的综合评分策略，评价算子组合，得到每个算子的选择概率，并进行更新；
S405.判断迭代过程中是否出现过此局部最优解，若是，则对算子组合进行减分，若否，则对算子组合进行加分；
S406.判断当前迭代次数是否大于最大允许迭代次数，若否，则更新迭代次数，Gen→Gen+1，重复S401-S406，若是，则迭代终止。
2.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，步骤S1中，
(101)配送路径成本中配送路径长度是外卖配送员从当前位置出发完成所有订单取餐和送餐任务的配送路线长度，xijk是0-1变量，为1时代表骑手k从i点行驶到j点，否则为0；dij表示点i和点j之间的距离，c0代表单位距离配送费用；配送路径成本的数学表达式为：
(102)发车成本包括骑手半固定成本、辅助支持成本；
骑手半固定成本包括完成固定工资以及配套工具费用，配套工具费用包括工装费用、培训费用、车辆费用以及相关的设备费用；
辅助支持成本包括技术研发投入成本、系统支持成本、相关人员参与成本、广告营销成本；
用C1表示发车成本，为骑手半固定成本与辅助支持成本之和，发车成本的高低与骑手车辆数正相关，yk是决策变量，如果骑手k参与配送则为1，否则为0；其数学表达式为：
(103)顾客满意度损失成本
在当前订单能够拆分的配餐环境下，影响顾客满意度的因素包括：骑手对同一地址分批送的时间间隔和骑手对同一地址的配送次数；Zr j是决策变量，Zr j＝1，代表r订单包含j送餐需求，否则不包含；其中j∈Cn，r∈Dm；Fj表示订单j实际送达的时间，Ej min表示顾客对订单j期待送达的时间；顾客满意度损失成本的数学表达式为：
3.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，外卖配送优化模型的目标函数为
约束条件有：
xijk＝0 or 1 (19)
其中，Vk表示骑手车辆集合，{1，2，3...,k}；Bn表示外卖取餐需求集合，{1，2，3...,n}；Cn表示外卖送餐需求集合，{n+1，n+1，n+3...,2n}；Dm表示订单集合，{1,2,3...，m}；c表示顾客满意度损失成本转化系数；Q0代表最大载重量；qi、qj为正代表送餐需求i、j所对应的需求量，为负代表取餐需求i、j所对应的供给量；Qi k、Qj k分别代表骑手k在i、j需求点的装载情况；Ti k、Tj k分别表示i、j需求被骑手k完成服务时刻，其中i∈Bn，Cn，k∈Vk；Wij表示i需求与j需求被同一骑手先后满足时，i需求所对应的外卖商家的等待时间，其中i，j∈Bn，Cn；tk ij表示棋手k从位置i到位置j的所用时长，其中i,j∈Bn，Cn；Ei表示i需求所对应的外卖商家的最早接受服务时间，其中i∈Bn，Cn；Li表示i需求所对应的外卖商家的最晚接受服务时间，其中i∈Bn，Cn；M表示一个很大的常数；外卖商家也即顾客；
式(4)表示车辆总成本最小；其中，式(5)代表每个配送需求都要得到满足；式(6)代表每个骑手车辆如果离开配送中心，最终必须返回配送中心；式(7)和式(8)是骑手车辆能够闲置；式(9)代表流量守恒限制；式(10)和式(11)是外卖配送需求一一对应约束，并且外卖商家要在外卖顾客之前被访问；式(12)表示车辆访问必须满足需求点的时间窗限制；式(13)表示车辆到达时刻限制；式(14)和式(15)代表车辆各配送点装载约束；式(16)记录k骑手是否发车；式(17)记录车辆完成配送需求时刻；式(18)记录每个订单的最早被访问时间。
4.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，步骤S3中，利用节约里程法产生初始解的过程如下：
首先选择适合车辆路径问题的整数编码方式，具体方式为：将外卖顾客的订单按商家进行拆分，形成N对配送需求，再将配送需求按照骑手满足顺序进行整数编码；解码过程与编码过程相反，根据需求对应关系找到相对应外卖顾客与外卖商家；
其次构造初始解，步骤如下：
(401)假设D为所有未分配车辆的外卖客户需求对集合；
(402)计算D中每个客户在满足时间窗以及载重约束下的最小插入成本与次小插入成本，找出次小插入成本与最小插入成本差值最大的客户对i，将其插入当前车辆，若当前没有客户能插入，则新安排一辆车，继续插入；
(403)将D集合中移除步骤(402)中找到的客户对i；
(404)如果D集合为空，则初始解构造完成，否则重复步骤(402)和(403)。
5.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，所述移除算子包括：
(1)随机移除算子
随机移除算子指随机从已经分配好的路径中移除若干个客户，然后放入移除列表中，移除数量通过参数N控制，共将N对客户移除放入新的列表中；具体做法为，首先选择N个不同的送货点作为待移除对象，找到相对应得取货点，将这N对客户都移除并放入待插入列表中，完成移除过程；送货点对应外卖顾客，取货点对应外卖商家；
(2)最大距离移除算子
最大距离移除算子是将造成总距离增加最多的客户组合移除出来，每个客户组合的距离为移除前路径总距离与移除后的路径总距离之差；所移除的数量同样受参数N控制，重复移除N次，将移除的所有客户放入新集合中；
(3)路径移除算子
路径移除算子是随机拆散一条已经构建好的路径，将路径内所有客户添加到移除集合中；
(4)需求组合相似移除算子
需求相似移除算子是根据需求的相似性进行移除的算子，首先从当前解中随机移除一个需求客户组合，随后将在需求组合上与该客户组合需求量的大小相差最小的N-1个客户组合移除；最终移除的数量由参数N决定；需求相似移除算子是为找寻可替代或两两可交换位置的客户集合，通过需求相似移除客户点，能够加快算法的收敛；
(5)到达时间窗相似移除算子
时间窗相似移除算子指首先随机移除一个客户，然后将在车辆到达其他客户时间与到达该客户时间相差最小的N-1个客户进行移除；
(6)集中移除算子
集中移除算子是根据客户的位置，将外卖顾客按照距离进行聚类，然后随机移除一个集中区域的N个外卖顾客，同时移除外卖顾客所对应的外卖商家；移除的数量为N；集中移除算子需要预先设计集中区域。
6.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，所述插入算子包括：
(1)贪婪插入算子
贪婪插入算子是指计算移除集合中每个客户插入所需要的代价，将代价最小的客户最先插入到部分解路径中，在移除集合中删除该客户，重新计算，直到移除集合为空；
(2)最大代价差插入算子
最大代价差插入算子是指计算移除集合中每个客户插入所需要的最小代价与次小代价，将代价差最大的客户插入到路径中，在移除集合中删除该客户，重新计算，直到移除集合为空。
7.根据权利要求1所述一种基于一单多商情形下的城市电商外卖配送路径优化方法，其特征在于，步骤S404中，基于现实配送特点，设计了综合评分法为每个算子计算分数，并加入挥发机制，历史分数占比会越来越小，具体设计如下：
(1)算子选择
使用若干种移除算子和插入算子混合进行算法优化，每次迭代根据分数情况来选择使用何种移除算子和插入算子；其中，分数越高，算子被选择出来的概率越大，首先根据分数选择使用何种移除算子进行移除，然后选择使用何种插入算子进行重插入操作；
(2)综合评分法
算子的选择概率是通过算子的评分确定的，算子的评分越高越容易被选择；通过C1、C2、C3既代表评分加成也代表评分等级，fn(C)代表下一次迭代中算子C的评分情况，fn(总)代表下一次迭代与C算子类型一样的所有移除算子或插入算子的最终评分之和，其中C1>C2>C3，n指第n代；具体解释为：当新得到的新解比历史最优解更好时，当前所使用的移除算子和重插入算子的分数增加C1；当新解不优于历史最优解但优于当前解时，当前所使用的移除算子和重插入算子分数增加C2；当新解不优于历史最优解也不优于当前解时，但历史迭代未出现过，则当前所使用的移除算子和重插入算子分数增加C3，其他情况不加分；
(3)挥发机制
挥发机制指的是每次迭代后，所有算子的分数需要乘以百分数h，0<h<1。
8.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现权利要求1至7任一项所述基于一单多商情形下的城市电商外卖配送路径优化方法的步骤。
9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该计算机程序被处理器执行时实现权利要求1至7任一项所述基于一单多商情形下的城市电商外卖配送路径优化方法的步骤。
CN202410221081.1A 2024-02-28 2024-02-28 基于一单多商情形下的城市电商外卖配送路径优化方法 Pending CN118134372A (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202410221081.1A CN118134372A (zh) 2024-02-28 2024-02-28 基于一单多商情形下的城市电商外卖配送路径优化方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202410221081.1A CN118134372A (zh) 2024-02-28 2024-02-28 基于一单多商情形下的城市电商外卖配送路径优化方法

Publications (1)

Publication Number Publication Date
CN118134372A true CN118134372A (zh) 2024-06-04

Family

ID=91244911

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202410221081.1A Pending CN118134372A (zh) 2024-02-28 2024-02-28 基于一单多商情形下的城市电商外卖配送路径优化方法

Country Status (1)

Country Link
CN (1) CN118134372A (zh)

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP3806007A1 (en) * 2019-10-09 2021-04-14 Bayerische Motoren Werke Aktiengesellschaft Methods, computer programs and systems for assigning vehicles to vehicular tasks and for providing a machine-learning model
CN114707693A (zh) * 2022-02-21 2022-07-05 山东科技大学 一种车辆配送路径规划方法及系统
US20230084312A1 (en) * 2020-02-21 2023-03-16 Beijing Jingdong Zhenshi Information Technology Co., Ltd. Route determination method, apparatus, server and storage medium for cold chain distribution
CN116703291A (zh) * 2023-06-15 2023-09-05 北京化工大学 一种混合能源车队配送路径优化方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP3806007A1 (en) * 2019-10-09 2021-04-14 Bayerische Motoren Werke Aktiengesellschaft Methods, computer programs and systems for assigning vehicles to vehicular tasks and for providing a machine-learning model
US20230084312A1 (en) * 2020-02-21 2023-03-16 Beijing Jingdong Zhenshi Information Technology Co., Ltd. Route determination method, apparatus, server and storage medium for cold chain distribution
CN114707693A (zh) * 2022-02-21 2022-07-05 山东科技大学 一种车辆配送路径规划方法及系统
CN116703291A (zh) * 2023-06-15 2023-09-05 北京化工大学 一种混合能源车队配送路径优化方法

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
STEFAN ROPKE: "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows", TRANSPORTATION SCIENCE, vol. 40, no. 4, 1 November 2006 (2006-11-01) *
史晓雯: "外卖与快递共同配送场景下订单分配及路径规划研究", 万方期刊, 12 May 2022 (2022-05-12) *
孙靖璐: "基于改进自适应大邻域搜索算法的带时间窗车辆路径问题研究", 《中国优秀硕士学位论文全文数据库 工程科技Ⅱ辑(月刊)》, no. 7, 15 July 2023 (2023-07-15) *
李珍萍: "共同配送选址-路径问题及大邻域搜索算法", 系统仿真学报, vol. 33, no. 10, 18 October 2021 (2021-10-18) *

Similar Documents

Publication Publication Date Title
CN110097234B (zh) 工业卷烟运输智能调度方法及系统
CN112288166A (zh) 基于遗传-模拟退火组合算法对物流配送的优化方法
CN102136104A (zh) 基于负载均衡和lk算法的车辆路径规划方法
CN114037180B (zh) 一种基于分支定价切割算法的协同配送路径优化方法
CN110705741B (zh) 一种基于改进蚁群算法的多配送中心车辆路径优化方法
CN113469416A (zh) 一种派件任务规划方法及设备
CN111445094B (zh) 一种结合时间要求的快递车辆路径优化的方法及系统
CN114912740A (zh) 一种按需出行智能决策方法和系统
Huang et al. Integrated sustainable planning of micro-hub network with mixed routing strategy
Zhen et al. Heterogeneous instant delivery orders scheduling and routing problem
Du et al. CrowDNet: Enabling a crowdsourced object delivery network based on modern portfolio theory
Hua et al. Optimality-guaranteed algorithms on the dynamic shared-taxi problem
CN114677087A (zh) 一种车辆组合无人机协同配送方法
Liu et al. A construction-and-repair based method for vehicle scheduling of bus line with branch lines
CN117035897B (zh) 一种即时配送平台骑手抢单方法
CN111553532B (zh) 一种城市快递车辆路径优化的方法及系统
Cui et al. A Time‐Dependent Vehicle Routing Problem for Instant Delivery Based on Memetic Algorithm
Arias-Melia et al. The vehicle sharing and task allocation problem: MILP formulation and a heuristic solution approach
CN118134372A (zh) 基于一单多商情形下的城市电商外卖配送路径优化方法
Zhang et al. Shared bikes scheduling under users’ travel uncertainty
Shen et al. A MultiObjective optimization approach for integrated timetabling and vehicle scheduling with uncertainty
Wang et al. A full service model for vehicle scheduling in one-way electric vehicle car-sharing systems
Wang et al. An Exact Method for a First-Mile Ridesharing Problem
Sunarso et al. The Impact of Consolidating On-Demand Food Delivery on Sustainability: A Simulation Study
Meng et al. Variable neighbourhood search based on Metropolis criterion for crowdsourced delivery scheduling problem in dispatch model

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination