The single-node dynamic service scheduling and dispatching problem
The single-node dynamic service scheduling and dispatching problem
复制标题
DOI：
10.1016/j.ejor.2004.06.016
复制
发表时间：
2006-04
期刊：
影响因子：
--
通讯作者：
Leonardo Campo Dall'Orto;T. Crainic;J. Leal;Warrren B Powell
中科院分区：
文献类型：
--
作者：
Leonardo Campo Dall'Orto;T. Crainic;J. Leal;Warrren B Powell
在本文中，我们关注动态服务网络设计（DSND）问题的一个特殊版本，即单终端向多个客户和其他终端调度服务的情况。我们提出了一个时间依赖的随机公式，旨在在给定的规划范围内优化问题，并提出了一种基于动态规划原理的解决方法。我们还提出了一个静态的、单周期的、单节点问题的公式，在处理时间依赖版本和一般服务网络设计案例时，它作为子问题出现。尽管它看起来很简单，但它仍然是一个网络设计问题，精确的求解方法不够快。因此，我们提出了两种基于弹出链概念的禁忌搜索元启发式方法。我们还引入了一种学习机制，利用在重复执行中收集的经验。实例实验表明，所提出的求解方法是有效的，并能得到较好的解。
In this paper, we focus on a particular version of the dynamic service network design (DSND) problem, namely the case of a single-terminal that dispatches services to a number of customers and other terminals. We present a time-dependent, stochastic formulation that aims to optimize the problem over a given planning horizon, and propose a solution approach based on dynamic programming principles. We also present a static, single-period, formulation of the single-node problem that appears as a subproblem when addressing the time-dependent version and general service network design cases. Despite its apparent simplicity, it is still a network design problem and exact solution methods are not sufficiently fast. We therefore propose two tabu search meta-heuristics based on the ejection-chain concept. We also introduce a learning mechanism that takes advantage of experience gathered in repeated executions. Experiments with problem instances derived from real cases indicate that the proposed solution methods are efficient and yield good solutions.