公共自行车的调度算法

cfan2021

公共自行车投入使用一段时间之后，

停放在每个停车点的自行车数量往往会出现不均衡的状况，

需要开一辆调度车把一些自行车从一个停车点搬运到另一个停车点，

使得每个停车点的自行车数量重新达到平衡状态。

假设该城市有n*n个正方形建筑，

建筑与建筑之间的空隙是道路，

这些道路一共有(n+1)*(n+1)个交叉点，

自行车的停车点都位于正方形的某条边的中点，

如下图所示：



其中正数表示该停车点停放的自行车过多（需要运走多少辆），

负数表示该停车点停放的自行车过少（需要补充多少辆），

所有正数和负数的总和为0。

红色圆圈表示调度车的起点和终点

（调度车工作完成后需要回到该点）。

假设调度车一开始是空的，

它能装下无限多辆自行车。

它每开到一个停车点，

就可以装载若干辆自行车，

或者卸下它已经装载过的若干辆自行车。

调度车必需在道路的右侧行驶，

驶到交叉点处才能调头或拐弯。

我们希望好好规划调度车的行进路线，

使得每个停车点的自行车数量全部达到平衡状态，

并且调度车走过的路程要尽可能少。

有什么比较好的算法去解决这个问题呢？

anadavetag

负数点能否＂借＂车，最后再还回来？

IsacSes

如果能的话，就转化成中国邮递员问题了。

我比较关注不能“借”的情况。

igikzari

那就意味着先有正后有负，且从头开始的任意长连续累加和均为非负。能否先求出所有满足要求的排序，再找最短路径。

IsacSes

或者先考虑正数的回路，再考虑如何插入负数，使得总路径尽可能短。

Elishslots

滴滴单车公司码农？哈哈

Zpasarbola

负数点不能向邻近点＂借＂车。即调度车不能搬运小于等于0的点的车。