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

Previous Articles Next Articles

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

CLC Number:

90B35
90C11

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics

Comments

[1]	Yu-Zhong Zhang, Shu-Guang Li. Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints [J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.
[2]	Imen Hamdi, Mohamed Fadhel Tekaya. A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem [J]. Journal of the Operations Research Society of China, 2020, 8(3): 457-476.
[3]	Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.
[4]	Wen-Chang Luo. On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs [J]. Journal of the Operations Research Society of China, 2020, 8(1): 165-175.
[5]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[6]	Long Wan, Jin-Jiang Yuan. Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems [J]. Journal of the Operations Research Society of China, 2019, 7(3): 485-500.
[7]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.