A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem
A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem
复制标题
DOI：
10.1287/trsc.14.2.130
复制
发表时间：
1980-05
影响因子：
4.6
通讯作者：
H. Psaraftis
中科院分区：
文献类型：
--
作者：
H. Psaraftis
调查的单车，多对多，立即要求拨号乘车问题的开发分为两个部分I和II。第一部分重点讨论问题的“静态”情况。在这种情况下，不考虑在路由执行期间可能出现的中间请求。一个广义的目标函数进行检查，最小化的加权组合的时间，以服务所有客户和他们所经历的“不满”的总程度，而等待服务。这种不满意被假定为是一个线性函数的等待和乘坐时间的每个客户。车辆容量限制和特殊优先规则是问题的一部分。开发了一种动态规划方法。该算法表现出的计算工作，虽然问题的大小的指数函数，是渐近低于相应的努力的经典动态规划算法应用于旅行推销员问题的相同大小。第二部分将这种方法扩展到解决等效的“动态”情况。在这种情况下，新的客户请求在发生时自动符合考虑条件。该程序是一个开放式的更新序列，每次更新都遵循每个新客户的请求。该算法仅对已知输入进行优化，并且不预测未来的客户请求。第一部分介绍的优先权规则防止无限期推迟客户的请求。在“静态”和“动态”的情况下的例子。
An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts I and II. Part I focuses on the “static” case of the problem. In this case, intermediate requests that may appear during the execution of the route are not considered. A generalized objective function is examined, the minimization of a weighted combination of the time to service all customers and of the total degree of “dissatisfaction” experienced by them while waiting for service. This dissatisfaction is assumed to be a linear function of the waiting and riding times of each customer. Vehicle capacity constraints and special priority rules are part of the problem. A Dynamic Programming approach is developed. The algorithm exhibits a computational effort which, although an exponential function of the size of the problem, is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size. Part II extends this approach to solving the equivalent “dynamic” case. In this case, new customer requests are automatically eligible for consideration at the time they occur. The procedure is an open-ended sequence of updates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests. Indefinite deferment of a customer's request is prevented by the priority rules introduced in Part I. Examples in both “static” and “dynamic” cases are presented.