题目说明
你要为宅配驾驶员制定一天的配送计划。输入给出有向道路网络、车辆停车位置、包裹的收件地点与指定时间条件,以及台车容量。车辆沿有向道路行驶;驾驶员可在停车点下车,把若干包裹装上台车,沿道路双向步行完成投递,再回到车辆继续行驶。
请输出车辆和台车的完整行动序列,在时间限制内尽可能多且尽可能早地完成配送。每个包裹最多投递一次;驾驶、停车、装卸、步行和交付都计入经过时间。
可行计划
- 车辆只能沿允许方向移动,并只能在候选停车位置开始台车行程。
- 台车可双向步行,但每次必须从车辆所在停车点出发并回到车辆。
- 一次装载的包裹数不得超过容量,送达后从载荷中移除。
- 动作按输出顺序执行,后一动作不得早于前一动作结束。
- 无法在评测期限内送达的包裹可以不送,但不得输出矛盾或重复投递。
输入与输出
输入包含道路拓扑与长度、停车点、包裹目的地、包裹时间条件、台车容量和评测时间范围。输出为按时间排序的行动记录,描述车辆驶向的停车点、每次装载的包裹以及台车访问收件点的顺序。编号均沿用输入编号。
评分
合法方案按完成投递的数量及完成时刻计分:完成更多包裹、在指定时段内更早完成可获得更高分;违反移动、容量或时间约束的行动不会形成有效投递,严重格式错误会使方案无效。目标是最大化总得分。