combinatorial optimization

A Crew Scheduling Problem (CSP) is a highly complex airline optimization problem, which includes two sub-problems, namely Crew Rostering Problem (CRP) and Crew Pairing Problem (CPP). Solving these problems sequentially may not lead to an optimal solution. To overcome this shortcoming, the present study introduces a new bi-objective formulation for the integrating CPP and CRP by considering the reserve crew with the objectives of crew cost minimization and crew reserve maximization. The integrated model generates and assigns pairings to a group of crew members by taking into account the rules and regulations about employing the manpower (i.e., crew member) and crew reservation in order to reduce flight delays or even cancellations due to the unexpected disruptions. An Ant Colony Optimization (ACO) algorithm is used to solve the considered problem. To justify the efficiency of this proposed algorithm in solving the presented model, different test problems are generated and solved by ACO and GAMS. The computational results indicate that solutions obtained by the proposed ACO algorithm have a 2.57% gap with the optimal solutions reported by GAMS as optimization software on average and significantly less CPU time for small-sized problems. Also, ACO obtains better solutions in significantly shorter CPU time for large-sized problems. The results indicate the efficient performance of the proposed algorithm in solving the given problems.

For this paper, we explored the implementation of the cuckoo search algorithm applied to the capacitated vehicle routing problem. The cuckoo search algorithm was implemented with Lévy flights with the 2-opt and double-bridge operations, and with 500 iterations for each run. The algorithm was tested on the problem instances from the Augerat benchmark dataset. The algorithm did not perform well on the problem instances, save for a select few on which the algorithm achieved the close to near-optimal result and one on which the algorithm achieved the optimal result. Increasing the number of iterations for each run of the algorithm on the two large-scale problem instances led to obtaining solutions closer to the optimal solution compared to the ones obtained with fewer number iterations. This gives an idea that the larger the problem instance becomes, the slower the algorithm converges to the optimal solution. Several other factors may also have contributed to the overall performance of the algorithm. Regardless of its performance, the algorithm was able to obtain routes that satisfied the constraints of the capacitated vehicle routing problem. The potential of the cuckoo search algorithm in solving combinatorial problems is demonstrated in this study in which the performance of the algorithm on routing problems was explored.

The school bus routing problem (SBRP) represents a variant of the well-known vehicle routing problem. The main goal of this study is to pick up students allocated to some bus stops and generate routes, including the selected stops, in order to carry students to school. In this paper, we have proposed a simple but effective metaheuristic approach that employs two features: first, it utilizes large neighborhood structures for a deeper exploration of the search space; second, the proposed heuristic executes an efficient transition between the feasible and infeasible portions of the search space. Exploration of the infeasible area is controlled by a dynamic penalty function to convert the unfeasible solution into a feasible one. Two metaheuristics, called N-ILS (a variant of the Nearest Neighbourhood with Iterated Local Search algorithm) and I-ILS (a variant of Insertion with Iterated Local Search algorithm) are proposed to solve SBRP. Our experimental procedure is based on the two data sets. The results show that N-ILS is able to obtain better solutions in shorter computing times. Additionally, N-ILS appears to be very competitive in comparison with the best existing metaheuristics suggested for SBRP

In this paper, a new genetic algorithm (GA) is presented for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. A random key and the related mode list (ML) representation scheme are used as encoding schemes and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. In this paper, a simple, efficient fitness function is proposed which has better performance compared to the other fitness functions in the literature. Defining a new mutation operator for ML is the other contribution of the current study. Comparing the results of the proposed GA with other approaches using the well-known benchmark sets in PSPLIB validates the effectiveness of the proposed algorithm to solve the MRCPSP.