# 派单进化算法

**Repository Path**: amtech/disp_deap

## Basic Information

- **Project Name**: 派单进化算法
- **Description**: 使用进化算法实现的智能派单，目前看来用不上了，分享给大家，希望能帮到有需要的人
- **Primary Language**: Python
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 8
- **Created**: 2023-05-11
- **Last Updated**: 2024-05-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 某上门服务平台派单算法

上门派单的需求：

1.用户会提前预约手艺人上门服务；
2.手艺人的时间和距离都是需要考虑的约束；
3.系统计算最优约束，使得手艺人产生的价值最大；

## 原理

在订单生成，手艺人还没上门前的间歇，通过算法安排最合适的手艺人及最合适的时间上门

将手艺人的时间库存及距离同时考虑，通过进化算法，在有限的时间内，找到区域内价值最优的对象和服务

### 计算资源

1.数据使用阿里云ods存储；
2.手艺人地理信息通过高德地图获取；
3.订单和时间信息通过数据库获取；

### 算法选型

使用evolutionary algorithm  py-ga-VRPMV 构建
deap框架构建

##  数据说明：

输入数据要求：

    1.全天以半小时为刻度的手艺人时间库存数组
    2.不可用时间用-1表示（包括无效和关闭时间）
    3.可约时间用0表示
    4.已约时间用入模订单的序号表示

示例如下：

    [1, -1, 0, 157, 157, 157, 157, 157, 0, 412, 412, 412, 412, 412, 0, 640, 640, 640, 640, 640, 0, 908, 908, 908, 908, 0]
    [53, 0, 0, 164, 164, 164, 164, 0, 0, 418, 418, 418, 418, 0, 0, 646, 646, 646, 646, 0, 0, 0, 0, 0, 0, -1]

## DNA编码交换过程：

    详见 _3_1_run_deap.py 代码中逻辑

## 项目文件夹说明

data    本地实验数据
gatspmv 进化算法的TSP问题求解器
gavrptw 进化算法带时间窗口的VRP问题求解器
geat    GEAT框架试验
instance_run_scripts    deap的示例
ortools ORTools框架试验
test    部分单元测试
tools   lbs相关工具
train       deap的训练试验
validate    deap的结果验证

### 计算逻辑

1.选取所有手艺人；

2.将所有订单地址随机分配给手艺人；

3.筛除不符合时间窗口条件的组合；

4.计算总路程时间；

    总消耗时间 = (路程时间 + 服务时间 + 缓冲时间)
    
### 找到优化的切入点

观察路程时间优化的较好的订单规律

### 注意事项：

    1.平台接单时间窗口不能动（路程时间最优）
    2.第三方渠道订单可以优化
    3.拿小城市跑（杭州）
    4.规则预留

## 使用说明

执行顺序：
    
    1.导出数据：1.exp_*.py
    2.数据准备：2.gen_*.py
    3.模型计算：3.run_*.py

或者一键执行：

    chmod +x run_all_v3
    ./run_all_v3

## 结果分析

见日志，目前观察都能在10轮迭代完成，暂定迭代次数为20次

## Reference to py-ga-VRPTW

- see iRB-Lab's [repository](https://github.com/iRB-Lab/py-ga-VRPTW)

## Debug 注意事项

    多线程的Python临时cache文件有问题，修改了代码后依然执行旧的逻辑

    每次执行前，需要手工删除 \_\_pycache__ 目录

    ps -ef|grep _3_1_run_deap|awk '{print $2}'|xargs kill -9

## 改进措施

1.针对北京、上海，订单密度较大的城市进行优化

2.针对目前优化的效果，将节约时间统计出来

## 问题

1.北京、上海 服务 类的优化时间较长，平均在1个小时

   主要原因是订单量较大，针对该范围的订单进行区域或商圈的分割
   business_district