论文部分内容阅读
城市物流为城市中的绝大部分活动提供支持,对城市的运行有着十分重要的影响。在城市物流中,客户需求往往具有较大的随机性,而且货物配送常常采用分区域管理的形式。在这种环境下,配送企业面临着如何将车辆分配到各个区域,使得在随机客户需求下的期望配送成本最小化的问题,本文针对这类运输资源分配问题进行研究。为了评估在指定车辆分配方案下系统的期望配送成本,本文在车辆路径问题的双下标双商品流混合整数规划模型的基础上构造了带有惩罚成本的车辆路径问题模型。此外,由于在配送成本的估计中需要求解许多不同需求情景下的车辆路径问题,需要大量的计算资源,所以本文采用仿真优化的方法,通过仿真估计在每一种车辆分配下每一个区域的期望配送成本,并通过优化算法将有限的仿真次数分配到各个区域和车辆数量的组合中。本文将仿真优化领域用于求解排序选择问题的无差异区间算法、最优计算分配算法和知识梯度算法推广到了运输资源分配问题的求解中。此外,本文还设计了敏感度分析算法。为了防止仿真误差导致算法陷入虚假的最优解,本文提出了探索/利用策略和方差的保守估计策略。由于在算法的求解中,需要多次计算在特定成本估计下运输资源分配问题的最优解,本文将其定义为确定性子问题进行研究。本文建立了确定性子问题的两种整数规划模型和一种动态规划模型,并指出在每个区域的配送成本均为关于车辆数量的单调递减的离散凸函数时,不但确定性子问题的整数规划模型的线性松弛可以得到整数最优解,而且确定性子问题可以通过贪婪算法求解。数值实验表明,知识梯度算法在求解中表现最佳,其次为敏感度分析算法和最优计算分配算法,基于无差异区间算法中Rinott算法的方差比例算法表现不够理想。本文提出的探索/利用策略和方差的保守估计策略对于提高算法的求解效率有显著的作用。