【论文笔记】Addressing the minimum fleet problem in on-demand urban mobility

66 阅读 0 评论 44 点赞

我是靠谱客的博主虚拟云朵，最近开发中收集的这篇文章主要介绍【论文笔记】Addressing the minimum fleet problem in on-demand urban mobility，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解决问题：一个城市统一调度需要多少辆车？一个仓库需要多少辆AGV完成调度？文章将这种不带pickup and delivery的VRP问题转化为二分图匹配问题，最大匹配等价于最少车辆数，既能解决车辆数，还能解决online的车辆调度。

中文翻译版本：http://www.sohu.com/a/235236660_260595

模型定义

如下图所示，二分图匹配中的每个节点都是一个trip，而每一个trip都由如下的四元组组成

而trip与trip之前的连线需要同时满足以下两个条件：

（1） $t_{i}^{d}+t_{ij}leqslant t_{j}^{p}$ ,其中 $t_{ij}$ 为两地的行驶时间，表示乘客无需等待可以乘车，车辆先到达乘车点

（2） $t_{j}^{p}-t_{i}^{d}leqslant delta$ ,表示trip与trip之间的空跑时间不能超过 $delta$ ，为可配置参数

求解可以采用匈牙利算法或者hopcroft-karp算法求解最大匹配，下图给出一个网上标准匈牙利算法的实现。

# coding:utf-8
import math
class Hungarian(object):
def find(self, x):
for i in range(self.n):
if self.graph[x][i] == 1 and not self.used[i]:
self.used[i] = 1
# 放入交替路
# self.used[x] = 1
if self.match[i] == -1 or self.find(self.match[i]) == 1:
self.match[i] = x
self.match[x] = i
# print(x + 1, '->', i + 1)
return 1
return 0
def hungarian1(self):
self.match = [-1] * self.n
# 记录匹配情况
self.used = [False] * self.n
# 记录是否访问过
m = 0
for i in range(self.n):
if self.match[i] == -1:
self.used = [False] * self.n
m += self.find(i)
return m
def process(self,matrixStr):
matrix = matrixStr.split(',')
matrixLen = int(math.sqrt(len(matrixStr.replace(',', ''))))
graph=[]
for i in range(matrixLen):
graph.append([0]*matrixLen +
map(lambda x:int(x),matrix[i * matrixLen:(i + 1) * matrixLen])
)
for i in range(matrixLen):
graph.append([0]*matrixLen*2)
for i in range(matrixLen):
for j in range(2*matrixLen):
value1=max(graph[i][j],graph[j][i])
graph[i][j]=value1
graph[j][i]=value1
self.graph = graph
self.n = len(graph)
m=self.hungarian1()
print (m,','.join( map(lambda x:str(x), self.match) ))
if __name__ == '__main__':
p = Hungarian()
matrix = '0,1,1,0,0,1,0,0,0'
p.process(matrix)