论文标题
自行车共享问题
The Bike Sharing Problem
论文作者
论文摘要
假设$ M \ geq 1 $自动移动代理和$ 0 \ leq b \ leq m $单机器运输设备（称为{\ em Bikes}）最初放置在单位间隔$ [0,1] $的左端$ 0 $的左端$ 0 $上。代理在能力上相同，可以以速度1的速度移动。自行车不能自行移动，但是任何骑自行车$ i $的代理商都可以以速度$ v_i> 1 $移动。代理商最多可以一次骑自行车。代理商可以通过分享自行车来合作；代理商可以骑自行车一段时间，然后将其丢弃以被另一个代理使用，并可能切换到其他自行车。 我们研究两个问题。在\ bs问题中，我们需要从间隔的左端开始的所有代理和自行车，以尽快到达间隔的末端。在\ RBS问题中，我们的目标是最大程度地减少代理商的到达时间；自行车可用于提高代理的平均速度，但不需要到达间隔的末端。 我们的主要结果是为\ bs问题构建多项式时间算法，该算法为旅行者和自行车跨间隔提供了到达时间的最佳时间表。对于\ rbs问题，我们给出了一种算法，该算法为最多可以放弃自行车的情况提供了最佳解决方案。
Assume that $m \geq 1$ autonomous mobile agents and $0 \leq b \leq m$ single-agent transportation devices (called {\em bikes}) are initially placed at the left endpoint $0$ of the unit interval $[0,1]$. The agents are identical in capability and can move at speed one. The bikes cannot move on their own, but any agent riding bike $i$ can move at speed $v_i > 1$. An agent may ride at most one bike at a time. The agents can cooperate by sharing the bikes; an agent can ride a bike for a time, then drop it to be used by another agent, and possibly switch to a different bike. We study two problems. In the \BS problem, we require all agents and bikes starting at the left endpoint of the interval to reach the end of the interval as soon as possible. In the \RBS problem, we aim to minimize the arrival time of the agents; the bikes can be used to increase the average speed of the agents, but are not required to reach the end of the interval. Our main result is the construction of a polynomial time algorithm for the \BS problem that creates an arrival-time optimal schedule for travellers and bikes to travel across the interval. For the \RBS problem, we give an algorithm that gives an optimal solution for the case when at most one of the bikes can be abandoned.
