Polynomial-time Algorithm for Dock Re-allocation Problem in Bike Sharing System

• Item type: SIG Technical Reports(1)
• 公開日: 2018-11-05
• タイトル: Polynomial-time Algorithm for Dock Re-allocation Problem in Bike Sharing System
• タイトル / 言語: en
• タイトル: Polynomial-time Algorithm for Dock Re-allocation Problem in Bike Sharing System
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Industrial Engineering and Economics, Tokyo Institute of Technology
• 著者名: Akiyoshi, Shioura
• 著者名(英): Akiyoshi, Shioura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper we consider a nonlinear integer programming problem for re-allocation of dock capacity in a bike sharing system discussed by Freund et al. (2017). Our main result is to show that the re-allocation problem can be solved in polynomial time. Our approach is to decompose the problem into two subproblems by using a new parameter. We first show that the two subproblems have the same structure as a relaxation of the dock re-allocation problem, and can be solved by a proximity-scaling algorithm that runs in polynomial time. We then prove that the two subproblems have convexity with respect to the parameter, which makes it possible to find an optimal value of the parameter by binary search.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we consider a nonlinear integer programming problem for re-allocation of dock capacity in a bike sharing system discussed by Freund et al. (2017). Our main result is to show that the re-allocation problem can be solved in polynomial time. Our approach is to decompose the problem into two subproblems by using a new parameter. We first show that the two subproblems have the same structure as a relaxation of the dock re-allocation problem, and can be solved by a proximity-scaling algorithm that runs in polynomial time. We then prove that the two subproblems have convexity with respect to the parameter, which makes it possible to find an optimal value of the parameter by binary search.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-170, 号 3, p. 1-5, 発行日 2018-11-05
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会