基于模拟退火算法的订单分配优化模型的研究

摘要：随着互联网的快速发展，面向大众的服务类型手机应用越来越多，为降低企业经营成本、增强企业 的服务效率和提升服务质量，需要平台不断优化内部订单和服务人员的分配算法，本文章主要研究“58 到 家 ”上门服务平台的订单和家政服务人员的匹配优化问题。首先，本文针对订单服务平台的离线批量派单 模式，对实际问题进行了一定简化，利用运筹学、数学规划的知识建立了优化模型，针对优化模型的求解， 本文采用了模拟退火的启发式算法，利用Matlab 编程首先生成一个初始解，作为当前的最优解，紧接着对 当前解加一个随机扰动，得到一个新解，然后利用蒙特卡洛判断准则判断是否接受该解，接着规定迭代次 数，当达到迭代次数后，如果达到指定的目标值，则输出结果，该模型的特点在于结合数学线性规划和模 拟退火算法进一步增强了算法的可靠性和稳定性，该算法可用于求解更加复杂的非线性优化问题，但当面 对原始数据过大的问题时，可能出现收敛速度过慢，执行时间较长的问题。

关键词：模拟退火算法；优化模型；Matlab 编程;线性规划
 

 
一、引言
 
随着互联网技术的不断发展，我国涌现出了诸如美团外卖、滴滴打车和 58 同城等一大 批手机服务平台，这些手机 APP 极大地便捷了城市居民的日常生活。对于这些企业而言，订 单与服务单元之间的合理分配一直是相关领域的重点问题，所以采取合适的匹配机制对降低 企业经营成本、增强企业的服务效率和提升服务质量等方面意义重大。

“58 到家 ”就是“58 同城 ”旗下的高质量上门家政服务平台，为用户提供包括保洁、 保姆、月嫂等众多生活领域的服务，解决了城市居民的生活问题，缓解了人们的生活压力。 在平台运行过程中，平台旨在将订单与阿姨进行一对一的匹配任务，阿姨在任务规定的时间 内到达指定服务地点完成固定时间的服务工作，服务完成后再由平台进行新的任务分配。但 是在实际运行过程中，平台分配还需要考虑到包括阿姨的服务质量、客户和阿姨的地理位置、 订单量过多时的压单情况等各种问题，因此需要通过优化系统的分配算法，提高平台的求解 效率，实现提升客户体验和节省阿姨时间的目的。

本次优化主要有两个目标：一方面，为提升对客户的服务质量，尽可能分配服务分较高 的阿姨（阿姨的服务分是基于阿姨历史订单的评价得到的，取值为[0，1],值越大表明阿姨 的服务质量越高）；另一方面，为节省阿姨时间，提高阿姨的接单量，尽可能缩短阿姨两单 之间的通行时间。

二、数据获取
 
2.1 原始数据集介绍

 本次问题材料统计了“58 同城 ”平台一天内、一个地区的所有订单和所有阿姨的信息， 包括订单的下单时间、订单服务开始的最早时间、订单服务开始的最晚时间、订单的服务时 长、订单的坐标、阿姨的服务分和阿姨的初始坐标等信息。原始数据的具体字段名和含义如 下：

表 2.1 原始数据及字段名说明
 

字段名	字段符号	字段含义
下单时间	createTime	客户在平台的下单时间 ，单位秒
最早服务时间	serviceFirstTime	客户接受的服务开始的最早时间， 单位秒
最晚服务时间	serviceLastTime	客户接受的服务开始的最晚时间， 单位秒
服务时长	serviceUnitTime	客户预约的服务时长 ，单位分钟
服务地点横坐标	x	服务地点横坐标 ，单位米
服务地点纵坐标	y	服务地点纵坐标 ，单位米
服务分	serviceScore	阿姨服务分由顾客评价求得 ，取值 为 [0,1]值越大越好
阿姨横坐标	auntx	阿姨初始地点横坐标 ，单位米
阿姨纵坐标	aunty	阿姨初始地点纵坐标 ，单位米

 
2.2 数据可视化处理

平台一天内、一个地区的所有订单数量超过两千，平台签约保洁阿姨数目接近三千，数 量较大，导致订单产生的包括下单时间、最早服务时间、最晚服务时间、阿姨的地理位置和 阿姨的服务分等各项数据总量巨大，无法直观地看出数据的规律和特点，因此我们对数据进 行了可视化处理。

我们首先对订单的下单时间、最早服务时间和最晚服务时间进行可视化处理，绘制如下 的订单时间信息折线图，我们可以看出订单的序号是根据订单的下单时间顺序确定的，订单 下单得越早，相应的订单 id 越小，并且随着时间的推移，单位时间内订单的下单数量也越 大。所有订单的最早服务时间与最晚服务时间相近，差别不大。

 
五、模型建立与求解
 
5.1 求解思路

平台是离线批量派单模式，并且需要将规定数量的订单进行分配，为使得阿姨分配的服 务分尽可能大，所以尽量采用服务分较高的阿姨；为使得阿姨的平均通行距离尽可能小，所 以需要考虑到阿姨的初始位置到服务地点的位置之间的距离和阿姨完成订单后的位置到下 一个订单的位置之间距离，尽量为阿姨分配距离其当前位置较近的订单，减少阿姨的通行时 间；为使得阿姨的服务订单的平均间隔时间尽可能小，所以应该考虑到阿姨完成订单的时间 和订单所接受的最早最晚服务开始时间，尽量减小阿姨的服务时间间隔，提高阿姨的工作效 率。

该问题实质上是对订单和阿姨的分配优化问题，因此我们需要找到该优化问题的三要素 即决策变量、约束条件和目标函数来构建模型，考虑到该问题的数据较大，求解困难，所以 我们决定结合模拟退火启发式算法求解。

模拟退火算法属于启发式算法，可以分解为解空间、目标函数和初始化三部分，首先由 一个产生函数从当前解产生一个位于解空间的新解，一般由当前新解经过简单地变换即可产 生新解的方法；接着计算与新解所对应的目标函数差；随后判断新解是否被接受，判断的依 据是一个接受准则；最后当新解被确定接受时，再用新解代替当前解，这需将当前解中对应 于产生新解时的变换部分予以实现，并修正目标函数值即可求解。

5.2 模型构建 决策变量：

............略

 
六、模型评价
 
本次数学建模主要运用到的数学模型是模拟退火算法，主要功能是以一定的概率来接受 一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

模拟退火算法的优点是它的计算过程非常简单，通用，鲁棒性强，也可适用于并行处理， 可用于求解复杂的非线性优化问题；但其缺点也十分明显：它的收敛速度很慢，执行时间长， 如果提高降温速度，可能导致得不到全局最优解。

为缓解退火模型的缺陷，我们可以考虑到通过在算法中增加升温速度、增加记忆功能、 采用多次搜索策略或者结合其他搜索机制的算法进行优化改进。