Search

This paper addresses an open vehicle routing problem with predetermined time windows under uncertain travel times (OVRP-UT). A novel light-robust-optimization model is proposed by integrating the goal programming formulations with set-based descriptions of the problem data, which can enable as many customers as possible to meet their demands within a group of predetermined time windows. An effective memetic algorithm (MA) is presented for solving the OVRP-UT model. We design a heuristic-based initialization mechanism to generate an initial population with a high level of quality and diversity. We design a timely-vertices based crossover operator and mutation operator to give birth to the offspring with high quality and good structure built in the search process. We provide a hybrid selection mechanism and a population updating strategy to remain the diversity of the population. We develop a self-adapted crossover and mutation rate to help the MA suit the different phases during the search process. A comprehensive simulation experiment based on the 320 benchmark instances demonstrates the effectiveness of the proposed algorithm.

Distributed Permutation Flowshop Scheduling Problem (DPFSP) has become a hot issue in recent years. However, DPFSP with uncertain processing times (DPFSP_UPT) has not been addressed so far although real manufacturing systems often encounter various uncertain factors which make processing times uncertain. In this paper, two local-search based metaheuristics, i.e., an Iterated Greedy algorithm (sIG) and an Iterated Local Search algorithm (sILS), are presented to solve the DPFSP_UPT with makespan criterion. A robust model of expect-risk rule is used to describe the DPFSP_UPT. A valid heuristic based on the well-known NEH heuristic is proposed to initialize sIG and sILS. An acceleration algorithm is adapted to save computational efforts. A destruction procedure with dynamic sizes is presented to enhance the exploration capability for sIG. A feature with the characteristic that small changes in the solution can preserve the properties of good solutions in the iterative process is applied by sILS. Both sIG and sILS use multiple local search methods to produce promising solutions by exploiting diverse search areas. Extensive experiments show that the proposed sIG and sILS perform significantly better than the five competing algorithms adapted in the literature, but there is no significant difference between sIG and sILS and each has its own advantages for different instances.