公共自行车的调度算法
公共自行车投入使用一段时间之后，停放在每个停车点的自行车数量往往会出现不均衡的状况，
需要开一辆调度车把一些自行车从一个停车点搬运到另一个停车点，
使得每个停车点的自行车数量重新达到平衡状态。
假设该城市有n*n个正方形建筑，
建筑与建筑之间的空隙是道路，
这些道路一共有(n+1)*(n+1)个交叉点，
自行车的停车点都位于正方形的某条边的中点，
如下图所示：
其中正数表示该停车点停放的自行车过多（需要运走多少辆），
负数表示该停车点停放的自行车过少（需要补充多少辆），
所有正数和负数的总和为0。
红色圆圈表示调度车的起点和终点
（调度车工作完成后需要回到该点）。
假设调度车一开始是空的，
它能装下无限多辆自行车。
它每开到一个停车点，
就可以装载若干辆自行车，
或者卸下它已经装载过的若干辆自行车。
调度车必需在道路的右侧行驶，
驶到交叉点处才能调头或拐弯。
我们希望好好规划调度车的行进路线，
使得每个停车点的自行车数量全部达到平衡状态，
并且调度车走过的路程要尽可能少。
有什么比较好的算法去解决这个问题呢？ 负数点能否＂借＂车，最后再还回来？ aimisiyou 发表于 2021-3-29 08:38
负数点能否＂借＂车，最后再还回来？
如果能的话，就转化成中国邮递员问题了。
我比较关注不能“借”的情况。 本帖最后由 aimisiyou 于 2021-3-29 10:11 编辑
KeyTo9_Fans 发表于 2021-3-29 09:44
如果能的话，就转化成中国邮递员问题了。
我比较关注不能“借”的情况。
那就意味着先有正后有负，且从头开始的任意长连续累加和均为非负。能否先求出所有满足要求的排序，再找最短路径。 或者先考虑正数的回路，再考虑如何插入负数，使得总路径尽可能短。 滴滴单车公司码农？哈哈 负数点不能向邻近点＂借＂车。即调度车不能搬运小于等于0的点的车。
页:
[1]