A variable neighbourhood search approach for crew transportation problems

摘要

Transporting products from the depot to various destinations is a general problem in logistics world. However, complications arise when the objective is changed from transporting goods to transferring people, as both distance-related costs and man-hour loss must be taken into account. This paper presents a Variable Neighbourhood Search (VNS) based heuristic that helps route planners of an oil and gas exploration company identify a set of promising least-cost routes, including the implicit cost of man-hour loss. Such a heuristic is developed based on a combination of several well-known heuristics in a two-phase manner. More specifically, in the first phase, an initial solution is constructed by the least man-hour loss insertion method; then, it is further improved by a series of intra-route and inter-route exchanges in the latter phase - 2-opt is applied for intra-route improvement; lambda-interchange and b-cyclic k-transfer are performed for inter-route improvement. Compared with the actual plan, an improvement on both average travelled distance and man-hour loss reduction is evident, where the magnitude of savings depends on weights assigned to each criterion.