求指导：维修任务安排问题

xiaoyaosun

某个热水器维修站承接多个品牌的热水器维修任务，负责附图所示地区的维修事
项。图中黑线表示道路。该地区共有 70 个不同的小区，为简单起见，假设每个小区都
是长方形区域，边长也仅有两种规格：2000米、1000 米，如小区1 是边长 1000 米的正
方形区域；小区 3 是 2000 米×1000 米的长方形区域；小区 9 是边长为 2000 米的正方
形区域。也假设每个小区的出入口仅有一个，并且出入口均位于小区四边中某个边的中
点处。进出口的位置见附表 1。维修站位于 65 号小区的左上角。维修员的出行方式为
电瓶车，平均速度为 25公里/小时。
维修站接待保修、维修员上门维修的流程如下：保修电话记录每个报修信息，生成
任务清单。每个维修员早 8：00到维修站领取其所负责区域的维修单，下午6：00 之前
必须将当天已经完成的清单与未完成的清单交到维修站。热水器的报修事项相对稳定，
假设一共有 A、B、C、D、E、F、G、H 八类，各类事项的平均维修时间数据如下表。  
事项         A   B    C    D    E    F    G    H
维修时间    10  20  15  30  20  15  35  20
（分钟）

请按照所给信息，建立数学模型，回答下列问题。
（1）假设每个小区的报修客户住处随机分布在小区内。建立模型说明在一个规格
为a千米×b千米小区内维修所需总时间与小区大小、报修项目之间的关系。
（2）假设维修员 Z负责小区 1---小区 16 的所有维修任务。某天接到的报修单见附
表 2。该维修员应当如何安排，使得一天内能完成尽可能多的维修任务。
（3）客户在报修时往往会对维修人员上门时间有要求，假设可能的时间要求分为
三个时间段：上午（8：00-11：00）、午饭时间（11：00-13：00）、下午时间（13：00-18：
00）。在上一题中，每项报修要求时间见附表 3。该维修员应当如何安排，使得一天内
能完成最多的维修任务（维修人员的午饭时间可以在 11：00-13：00内灵活安排，时间
约为 30 分钟）。
（4）维修站承诺所有报修事项能在报修后 3 天内上门修理。假设今天是 2012年 5
月 4 日，维修站现在仍没有完成的维修任务以及报修时间如附表 4。按照当前任务，维
修站至少需要几名维修员，能够在承诺的时间内完成所有修理工作。
（5）客户在报修时只说明一项维修事项，而维修人员上门时往往发现维修项目并
不只是所报修的一项，历史修理情况统计数据见附表 5。请分析此情况对（4）题的影
响。

联系邮箱：wfyss6@gmail.com
请提供点思路，不胜感激~

amao

一问一问来吧。
只考虑主要因素的话，是个旅行商（TSP）问题。由于维修时间是不能更改的，所以，路上的时间越少，实际用于维修的时间就越长。
最后一问维修任务也不是事先确定的，这个就只能算概率了。

xiaoyaosun

回复 2# amao


    谢谢你，是旅行商问题哈？好的

amao

第一问是旅行商，但是后面与概率有关，就不那么简单了。
这是哪个学校的题目？


回复 3# xiaoyaosun

dianxiaoer

回复 4# amao


    第一问不用概率吗？第二问不是才是旅行商问题吗

amao

第一问说是随机分布，没有别的信息的情况下，先当成均匀分布。
第二问也是TSP。

回复  amao


    第一问不用概率吗？第二问不是才是旅行商问题吗
dianxiaoer 发表于 2012-5-18 21:05

dianxiaoer

回复 6# amao


    可是这个均匀分布的概率该怎么算呢，把客户当成小区内的任意一个点吗？这样概率怎么算呢？求灵感啊！