# PDPTW

**Repository Path**: kingsley_cl/PDPTW

## Basic Information

- **Project Name**: PDPTW
- **Description**: PDPTW求解算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2020-03-18
- **Last Updated**: 2023-11-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

PDPTW求解算法

实际和最迟开始服务时间(AC和LA)以各站点索引的哈希表记录

预先计算存储距离矩阵
改进Dist函数的参数形式

引入跳出局部函数
选择搜索方向时引入离散选择，选择PD对前后点时间差越大选择概率越高

将时差插入STI拆分为插入函数STI和重插入函数re_insert；STI返回所有可行情况，在re_insert等调用中再进行选择
将Problem中的Time函数拆分为求完成服务时刻和求总路程时间+等待时间
跳转函数jump中部分参数进行调整

Problem类和Solution类放一个module
Problem类有函数针对路线求车辆数和路线长度，Solution类目标函数同时求路线车辆数、长度和耗时，等待时间可由后两者求出故不予计算
STI只返回有效解，标记的无效解不返回
标记0的解将把原标记的无效方向清空，减少空间占用

随递归深度增加，选择方向时更倾向于移除代价落差大的方向
设置最大递归深度
修改部分错误标记
目标函数值传递dist和dura以三位小数的int形式存储
将多算例文件输出分离

STI引入参数num，只返回最优的num个解，不判定该解是否有进一步搜索价值
修复部分bug：
1、判定无效方向的逻辑，先判断解是否优化再判断其是否有搜索价值
2、route统一类型int
3、record数组两个set独立
4、record和count_insert归于Problem类，避免多算例一次计算的叠加

目标函数Aim依赖于AC值，故STI中需先更新AC再求Aim，最后再sort route避免j位置错误
引入函数求最长相互冲突序列base
jump时保持base不动，search中可动

修复逻辑bug，last_solu仅剩一个方向时也不可以标为None，因为下一点不一定只有一个搜索方向
初始解产生后先扰动再进行搜索
STI中检查容量约束，插入P后从本辆车第一站检查至i，若未超载则记录运载量，插入D后检查至j
引入参数num控制reinsert返回的最优解数量
中间计算时保留4位小数，保证最后保留三位小数的结果精度

STI中检查到i到j间路线不满足容量约束则退出j循环

修复lexsort的错误，lexsort默认以矩阵最后一行为依据排序
增加了求解结果csv文件
增加了获取实验数据的代码文件
增加了引入SA相关实验代码文件