本文是一篇物流工程论文，本文在考虑骑手异质性的前提下，对一个决策期内出现的订单根据送达时间和取送货点之间的相似性采用AP聚类和K-means聚类结合的方式进行聚类形成订单任务集合，之后以客户满意度最大化、配送成本最小化为原则建立相应的数学模型对订单集合进行分派和路径优化研究。
第一章绪论
1.1研究背景及意义
1.1.1研究背景
外卖，起初指的是销售给消费者的，可以允许消费者带离店里的商品[1]。后来外卖发展成为快餐商品的外送服务。随着智能手机和互联网的广泛普及，外卖行业的规模也得以扩大并进一步发展。各个外卖运营平台在市场竞争不断加剧的背景下均将满足客户即时需求为核心和主旨，通过使用互联网及大数据分析等相关工具致力于创造一个线上平台即时完成交易，线下高效完成商品或服务交付的模式来满足本地居民或用户生活需求。2020年公共卫生事件的突发，给外卖行业带来冲击的同时，也在一定程度上促使外卖行业积极转型，加快了线上线下模式的相互融合。外卖所经营的产品和服务也由原来传统的餐食不断扩展到了生活用品、医药用品等多个领域。外卖业务中主要用户群体大多是年轻人，年龄主要集中在18~25岁之间，其次是26~30岁[2]。当这类人群开始陆续加入到社会工作中去，在周末时他们更愿意待在家里用外卖来满足日常的生活餐饮需求。随着“懒人经济”冲上热搜，外卖也进一步得以蓬勃发展。况且随着居民消费水平的不断提升，对于餐食的高效便利以及餐食的安全性等相关需求不断提高，餐饮外卖已经发展成为外卖产品中的高频业务。
我国外卖行业的市场规模在2021年度达到7855.8亿元，同比增长了18.2%[3]，预计在2022年将达到9411.3亿元。在2022年我们外卖行业中人均消费支出为789.7元，与2021年相比增加了11.3%[4]。不仅如此外卖平台的业务收入以及订单交易量也在持续提高。从2017年开始美团团的主营业务收入以及外卖交易量均呈现一个逐步上升的趋势，并且有望在2023年度实现200亿元大关[5]！相应的，其在2015年~2022年度业务收入以及外卖交易量的数据如图1.1所示。截至2021年6月，美团平台开始推广无人机配送且目前已经完成大约22万架次的配送测试[6]。在未来，外卖配送也会有越来越多的新技术研发并逐步投入使用。
1.2国内外研究现状
从2011年开始，外卖配送开始出现在我国消费者的视野中，并随着越来越多的消费者选择外卖、认可外卖，才使得外卖行业逐步发展起来[10]。外卖配送作为即时配送的一种，也在发展的过程中逐步的受到了国内外学者的广泛关注，该问题的相关研究成果也逐步的丰富起来。
如图1.2所示，选择Web of Science以及中国知网（CNKI）为主要文献检索渠道，以谷歌学术、KCI、IEEE Xplore等文献数据库作为相应的补充，在英文文献数据库的检索词条为“Takeaway Delivery”、“Instant Delivery”及“Crowdsourced Delivery”，在中文文献数据库中则以“外卖配送”、“即时配送”和“众包配送”为检索词条，通过将各个数据库文献量进行统计后得到在该领域相关问题的研究文献发表量的趋势图。
第二章外卖平台现状分析
2.1外卖配送业务流程及主体
（1）相关主体
外卖的配送过程是一个多方主体共同参与的过程，是一个由线上下单，线下服务的一个复杂的过程。各个参与主体之间是相互联系，缺一不可的。整个外卖的流程中，外卖平台扮演着不可或缺的核心位置。外卖平台是商家和客户进行交易的平台，也是在配送各环节决策上的“大脑”。它也是各个主体活动相互联系的枢纽。经分析，外卖业务流程中涉及到商家、客户、骑手以及平台四大主体。
商家是主要负责为客户提供餐食，在接到订单后开始备餐并在规定时间的出餐保证订单准时性的前提。商家是为客户提供所需要的产品或服务的主体，商家一般都拥有线下实体店。商家入驻在平台上，在平台上接收来自不同客户不同需求的订单，并在一定时间内完成备餐后将餐食交给骑手负责进行后续的配送。客户是需求的提出端。
客户在平台上选择自己满意的产品并产生相应的订单，这是外卖业务的起点。客户是需求产生的主体，也是骑手、商家及平台的服务对象。当客户下单后，订单生成并会产生相应的配送任务，订单的相关信息回发送给平台及商家同步处理。一般来说，客户对于外卖配送的时效性、餐食的新鲜程度以及其余主体的服务水平要求相对较高。这其中，客户对外卖配送的准时与否以及商家的餐食新鲜程度等尤为重视。
骑手则是通过在平台的调度下负责从商家所在位置取走餐食后，在客户要求或是平台预计的送达时间内送到客户指定的地点。骑手是执行配送任务的主体。当客户下单订单后，骑手会先赶往商家所在位置进行取餐后将其送达对应的客户所在的位置。骑手的订单接受数量以及对应的配送路径有些是由外卖平台进行分配和调度的。
2.2外卖平台订单分配模式
外卖平台作为一个全局调度的窗口，也是连接商家和客户之间的桥梁。在外卖平台中存在个多个商家，为客户提供不同种类的餐品及服务，客户登录平台选择合适、能够满足其需求的餐品或服务，平台通过对相关的信息进行处理后调配合适的骑手为客户服务，完成相应订单的配送任务。在外卖平台中相应的骑手主要可以分为两者，一种是自有骑手，该类骑手由平台雇佣并由平台进行统一管理，他们是平台的正式员工，有固定的上下线时间；另外一种就是众包骑手，该类骑手主要是由社会闲散劳动力组成的，大多数为自由职业者、学生或是下班时间较为空闲的人员。此类骑手的上下线时间相对比较自由，主要是根据自身空闲时间的长短来进行对应的订单配送任务。在派单模式下，这一类骑手有一定拒单的可能性。这两类骑手的订单分配模式也有不同，自有骑手一般由平台派单，而众包骑手主要是通过在订单池中进行抢单来进行配送。但是也有相关的平台对他们均采用派单或是抢单的模式来分配订单。将骑手进行分类管理主要是为了防止在订单高峰期来临时运力不足导致大量订单的超时或是中断。
外卖平台中的派单模式如图2.3所示，在订单处理前期同抢单模式相同，先由客户在平台选择并下单后，由平台先将订单发送给商家，商家决定是否接受该订单。商家接受订单后，进行备餐的同时，平台处理订单。在某些情况下，平台会将订单配送业务外包给第三方企业，由第三方企业进行调度和路径规划。如果选择自有骑手配送时，平台根据骑手的实时状态及位置，订单与骑手的距离等方面进行综合考虑，将订单指派给合适的骑手进行配送并为其规划合适的配送路线。
第三章问题分析及模型建立..........................32
3.1问题描述及相关假设......................32
3.2参数设置及说明.....................................33
第四章三阶段求解策略.................................45
4.1订单组合求解.............................45
4.1.1订单组合规则.............................45
4.1.2聚类组合算法设计...........................45
第五章实例分析...............................57
5.1数据来源...........................57
5.2结果分析...........................58
第五章实例分析
5.1数据来源
通过在网上以及实地调查等方式，获取了某平台在某区域的2020年某一周内的外卖订单的历史数据。该数据是由某平台举办的智慧物流挑战赛的相关数据，数据具有一定程度的可信度。通过对于相关数据的分析，在某天的总订单数量最大达到了3695条，平台所保有可用于调度的骑手总有543个。经过计算可知，每个骑手平均配送的订单量为6-7个。对该平台的调研中发现，新骑手的订单延误所占比例较大，导致客户满意度的下降和延迟成本的大幅增加。因此需要考虑如何进行合理的运力调度来提升平台的客户服务质量。
根据对该平台的订单数据进行脱敏后我们可知，该平台的订单在10点到12点之间达到最大，下单人数也最多，因此我们选择在这个周期内出现的订单数据进行研究并求解。为了保证订单数据的准确性和有效性，再删去缺乏相关信息或是订单配送失败的订单，对剩余有效订单进行分析。尽管每天的外卖订单均会有高峰期出现，但是在高峰期不同的时间段内出现订单数量仍旧有较大差异，因此平台不同的订单调度时间内出现的订单数量也不同。为了验证模型及算法在外卖配送问题中的有效性，最终分别选择30、50、150个订单在一个订单调度周期内进行处理并分配，进而得出对应的订单组合、订单分派和路径规划结果，以便分析不同的订单规模下平台的运力配置和对成本及满意度的影响。订单中所包含的信息包括取送点各自的经纬度、预计送达时间、取餐时间以及是否购买“准时宝”、订单金额、订单超时的赔付比例等信息；骑手的相关信息包括各类型骑手的平均每公里运输成本、单均启动成本、配送速度、骑手初始位置及订单承载量等信息；客户订单的备餐时间一定，但是在客户处服务时间服从正态分布。另外，对于客户满意度的延迟时间与所对应的延迟成本的核算中，为了得出一定条件下的结论，参考目前外卖平台的赔付机制，分别设置为延迟10分钟、20分钟和30分钟，若超过30分钟，客户会拒绝订单，则延迟成本无限大。
第六章研究结论与展望
6.1研究结论
高峰期间出现的外卖订单如何高效及时的进行处理，包括对于订单任务的分配以及骑手配送路径的规划是亟待解决的问题。由于外卖订单出现后均包括取送货两个访问点且严格的访问顺序的约束，骑手登录配送系统后的初始位置是
