物流管理被称为"第三利润源泉",而中国物流作业时间几乎是加工时间的9倍,其中配送车调度是物流作业过程中的关键环节,它对于配送的速度、时间和效益有着直接的影响.该文在服务需求序列为未知的情况下,运用占线问题的研究技巧来研究配送车调度问题,以降低配送车服务时间,从而减少物流成本、提高配送效率.具体结论如下:一、将物流配送中的配送车调度问题运用占线问题的研究技巧进行分析,从而使得模型与结论更加贴近于现实.建立的占线配送车调度问题模型为:在一个具有n个顶点的有限网络上建立了s个配送中心,并且有k辆配送车在这个网络上进行送货服务,当需求一个接一个到达时,如何调度配送车使服务的总费用最少?当需求均为配送中心发出时,占线配送车调度问题称为P1(此情形下,所有的需求都是退化需求,问题P1亦称为k服务器问题);当需求均由需求点发出时,那么对应的占线k配送车调度问题为P2.该文给出问题P2所对应离线问题的DP求解方法.二、在分析模型的基础上给出了两种情况下的竞争策略.最后,通过对竞争比结果分析指出λ越趋近于1时,占线配送车调度问题竞争比越优;适当增加配送车数量,使得k≥min{s,n-s}时,采用复位策略,使得竞争比将会有较好的改善.三、给出在需求点具有限制条件时的占线配送车调度问题(P3),对离线最优调度时间进行了分析,并且对配送车数量不同的情况下给出相应的调度方案:四、最后给出需求点有p倍需求的占线DSP问题,并讨论了如下三个问题:一般占线配送车调度问题(P4)、限制条件下占线配送车调度问题(P5)和特殊网络图上的占线配送车调度问题(P6).对问题P4,应用贪婪策略得到竞争比为λ;对问题P5,应用贪婪复位策略得到竞争比为2+λ/2;对问题P6,给出两种策略:贪婪复位策略和平均复位策略,分别得到相应的竞争比,通过对竞争比的分析,可知当p