如何捆绑成对的旅行?

How to bundle pairs of trips?

我有一个可选的实时旅行需求数据库。每个都有可以从出发点运送到目的地的负载:

ID,EndDateEnd,EndDateStart,StartDateEnd,StartDateStart,DepX,DepY,ArrX,ArrY
1,2021-03-04,2021-03-03,2021-03-02,2021-03-01,2.83689,47.3324,-0.5854,44.83814
2,2021-03-04,2021-03-03,2021-03-02,2021-03-01,2.44774,47.56044,0.13888,49.49015
3,2021-03-10,2021-03-09,2021-03-08,2021-03-07,2.76755,47.97472,0.65567,48.78064
...

这是公司需要在特定地点和时间交付的负载报价列表。

我的目标是捆绑成对的货物以增加我的卡车的付费里程。我通常有一个固定的目的地和起点。假设我要从纽约市去芝加哥。然后我在行程数据库中搜索需要沿该路线运送的负载。想象一下,我找到了一个在匹兹堡取货并在克利夫兰送货的人。那么我的付费里程就是从匹兹堡到克利夫兰的行驶距离。但我从纽约到匹兹堡或从克利夫兰到芝加哥并没有得到报酬。最好有图说明:

蓝色是付费里程,红色是未付费里程。如果我能找到另一个从纽约到匹兹堡的负载,那就太好了,或者克利夫兰-芝加哥也是如此。

现在的问题是如何通过算法找到给定路线一起的负载对?我知道我的部分和旅行的终点。我只需要浏览旅行列表,找到最适合我的旅行。

-相处融洽是一个宽松的定义。一般来说,增加付费里程的百分比是目标。

我研究过的一个解决方案:

如果仅一辆卡车承担两种负载所行驶的里程少于两辆卡车承担每一种负载所行驶的英里数,则您可以定义两种负载“一起运行”。

这就是克拉克和赖特储蓄法背后的直觉。

正在做你最喜欢的距离函数。在我们的例子中,开始是纽约,结束是芝加哥。提货和送货来自候选的包裹对。如果储蓄高,那么它是一个很好的组合。


这是一种车辆路径问题,有时称为随时间取货和送货 windows(PDPTW) 我正在尝试解决其中的一小部分问题。只是找到有用的旅行对。

还有其他解决方案吗?可扩展的捆绑方法?

相关研究论文:

交叉post: https://or.stackexchange.com/questions/8159/how-to-bundle-pairs-of-trips

路由库中有pdptw例子:

Simple Pickup and Delivery problem in C++