著者

Vitor Mitsuo FUKUSHIGUE HAMA Wei WU Mutsunori YAGIURA

出版者

The Japan Society of Mechanical Engineers

雑誌

Journal of Advanced Mechanical Design, Systems, and Manufacturing (ISSN:18813054)

巻号頁・発行日

vol.12, no.3, pp.JAMDSM0072, 2018 (Released:2018-07-20)

参考文献数

29

---

The overall planning process undertaken by a bus company is traditionally composed of five sub-processes: timetabling, vehicle scheduling, maintenance scheduling, crew scheduling, and crew rostering. Solving the full optimization problem is believed to be computationally intractable, and therefore in practice the five sub-processes are usually optimized in sequence. In this paper, we present a model that integrates the problems of vehicle scheduling and maintenance scheduling. The objective is to minimize the differences in mileage between buses, the total distance traveled, and the daily differences in the number of maintenance tasks. We propose a heuristic algorithm using the framework of greedy randomized adaptive search procedure (GRASP), and we improve the neighborhood search procedure by using an ordered list of possible trips. We compare the neighborhood search procedure with and without this mechanism and show that the ordered list reduces the number of neighbors to be checked by more than 95%, and it reduces the time to obtain solutions of the same or better quality by an average of 70%. Through computational experiments on instances generated from real-world data, we show that the proposed algorithm finds solutions that are as good as or better than those obtained by a commercial solver in less than 5% of the time required by the latter.

著者

Yannan Hu Hideki Hashimoto Shinji Imahori Takeaki Uno Mutsunori Yagiura

出版者

日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.59, no.1, pp.110-129, 2016 (Released:2016-02-02)

参考文献数

17

被引用文献数

2

---

This paper focuses on a two-dimensional strip packing problem where a set of arbitrarily shaped rectilinear blocks need be packed into a larger rectangular container without overlap. A rectilinear block is a polygonal block whose interior angles are either 90∘or 270∘. This problem involves many industrial applications, such as VLSI design, timber/glass cutting, and newspaper layout. We generalized a bottom-left and a best-fit algorithms to the rectilinear block packing problem in our previous paper. Based on the analysis of the strength and weakness of these algorithms, we propose a new construction heuristic algorithm called the partition-based best-fit algorithm (PBF algorithm), which takes advantages of both the bottom-left and the best-fit algorithms. The basic idea of the PBF algorithm is that it partitions all the items into groups and then packs the items in a group-by-group manner. The best-fit algorithm is taken as the internal tactics for each group. The proposed algorithm is tested on a series of instances, which are generated from benchmark instances. The computational results show that the proposed algorithm significantly improves the performance of the existing construction heuristic algorithms and is especially effective for the instances having large differences in the sizes of given shapes.