A Novel MILP Model for N-vehicle Exploration Problem

doi:10.1007/s40305-019-00289-2

Journal of the Operations Research Society of China ›› 2021, Vol. 9 ›› Issue (2): 359-373.doi: 10.1007/s40305-019-00289-2

收稿日期:2019-02-20 修回日期:2019-07-25 出版日期:2021-06-30 发布日期:2021-06-08

A Novel MILP Model for N-vehicle Exploration Problem

Guo-Jun Zhang^1,2, Jin-Chuan Cui¹

1. Academy of mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
2. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Received:2019-02-20 Revised:2019-07-25 Online:2021-06-30 Published:2021-06-08
Contact: Guo-Jun Zhang, Jin-Chuan Cui E-mail:zgj@amss.ac.cn;cjc@amss.ac.cn
Supported by:
This work was supported by Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Science.

摘要/Abstract

Abstract: The N-vehicle exploration problem (NVEP) is a nonlinear discrete scheduling problem, and the complexity status remains open. To our knowledge, there is no literature until now employing mixed integer linear programming (MILP) technology to solve this problem except for Wang (J Oper Res Soc China 3(4):489–498, 2015). However, they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n³), which was inefficient to solve practical problems. This paper establishes a more concise MILP model, where the number of constraints is just O(n²). Therefore, the existing efficient MILP algorithms can be used to solve NVEP. Secondly, we provide some properties of N-vehicle problem and give three methods for cutting plane construction, which can increase the solving speed significantly. Finally, a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques.

Key words: N-vehicle exploration problem (NVEP), MILP, Cutting plane

中图分类号:

90B35
90C11

. [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.

Guo-Jun Zhang, Jin-Chuan Cui. A Novel MILP Model for N-vehicle Exploration Problem[J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.

参考文献

[1] Fine, J.: The jeep problem. Am. Math. Mon. 54, 24–31(1947)
[2] Woeginger, G.: Scheduling (dagstuhl seminar 10071). Dagstuhl Research Online Publication Server p. 24(2010)
[3] Carlier, J.: The one-machine sequencing problem. Eur. J. Oper. Res. 11, 42–47(1982)
[4] Liu, R., Lu, H., Cui, J., Li, X.: Studies on the heuristic algorithm for the N-vehicle exploration problem (NVEP). In: The Tenth International Symposium on Operations Research and Its Applications, pp. 107–114. Citeseer (2011)
[5] Höhn, W.: Scheduling (dagstuhl seminar 13111). Dagstuhl Research Online Publication Server pp. 32–33(2013)
[6] Li, X., Cui, J.: Real-time algorithm scheme for N-vehicle exploration problem. In: Combinatorial Optimization and Applications. In: Third International Conference, COCOA 2009, Huangshan, China, June 10–12, 2009. Proceedings, pp. 287–300. Springer, Berlin (2009)
[7] Xu, Y., Cui, J.: Multitask N-vehicle exploration problem: complexity and algorithm. J. Syst. Sci. Complex. 25(6), 1080–1092(2012)
[8] Xu, Y., Cui, J.: A kind of ε-approximation algorithm for the exploration problem with N-vehicles. Acta Math. Appl. Sin. 32(6), 1036–1043(2009)
[9] Li, X.: A kind of rollout algorithm for N-vehicles exploration problem. Acta Math. Appl. Sin. 37(1), 99–108(2014)
[10] Liu, A., Deng, X., Tong, Z., Xu, F., Liu, B., Duan, W., Li, Z.: A tabu-based variable neighborhood local search for n-vehicles exploration problem. In: Control and Automation (ICCA), 201612th IEEE International Conference on, pp. 951–955. IEEE (2016)
[11] Gamzu, I., Segev, D.: A polynomial-time approximation scheme for the airplane refueling problem. J. Sched. (2015). https://doi.org/10.1007/s10951-018-0569-x
[12] Wang, L.L., She, B.L., Liu, J.F., Cui, J.C.: A linear mixed integer programming model for N-vehicle exploration problem. J. Oper. Res. Soc. China 3(4), 489–498(2015)
[13] Vásquez,O.C.: For the airplane refueling problem local precedence implies global precedence. Optim. Lett. 9(4), 663–675(2015)
[14] Bansal, N., Dürr, C., Thang, N.K., Vásquez, O.C.: The local-global conjecture for scheduling with non-linear cost. J. Sched. 20(3), 239–254(2017)

A Novel MILP Model for N-vehicle Exploration Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价