• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Bike sharing systems: Solving the static rebalancing problem
【24h】

Bike sharing systems: Solving the static rebalancing problem

机译：自行车共享系统：解决静态平衡问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper deals with a new problem that is a generalization of the many to many pickup and delivery problem and which is motivated by operating self-service bike sharing systems. There is only one commodity, initially distributed among the vertices of a graph, and a capacitated single vehicle aims to redistribute the commodity in order to reach a target distribution. Each vertex can be visited several times and also can be used as a buffer in which the commodity is stored for a later visit. This problem is NP-hard, since it contains several NP-hard problems as special cases (the TSP being maybe the most obvious one). Even finding a tractable exact formulation remains problematic. This paper presents efficient algorithms for solving instances of reasonable size, and contains several theoretical results related to these algorithms. A branch-and-cut algorithm is proposed for solving a relaxation of the problem. An upper bound of the optimal solution of the problem is obtained by a tabu search, which is based on some theoretical properties of the solution, once fixed the sequence of the visited vertices. The possibility of using the information provided by the relaxation receives a special attention, both from a theoretical and a practical point of view. It is proven that to build a feasible solution of the problem by using the one obtained by the relaxation is an NP-hard problem. Nevertheless, a tabu search initialized with the optimal solution of the relaxation often shows that it is the optimal one. The algorithms have been tested on a set of instances coming from the literature, proving their effectiveness.
机译：本文讨论了一个新问题，该问题是多对多取货和送货问题的概括，并且是由操作自助自行车共享系统推动的。只有一种商品，最初会在图形的各个顶点之间分配，并且一个容量有限的单车旨在重新分配商品以达到目标分配。每个顶点可以被访问几次，也可以用作存储商品以供以后访问的缓冲区。此问题是NP难题，因为它包含几个特殊情况下的NP难题（TSP可能是最明显的问题）。即使找到易于处理的确切表述仍然是有问题的。本文提出了用于求解合理大小实例的有效算法，并包含与这些算法有关的一些理论结果。为了解决该问题，提出了一种分支切算法。一旦禁忌搜索顶点的序列，通过禁忌搜索获得问题的最佳解的上限，禁忌搜索基于解的某些理论属性。从理论和实践的角度来看，使用放松提供的信息的可能性都受到了特别的关注。事实证明，使用松弛法得到的问题的可行解决方案是一个NP难题。然而，用松弛的最佳解初始化的禁忌搜索常常表明它是最佳的。该算法已经在来自文献的一组实例上进行了测试，证明了其有效性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号