Iterated local search for the team orienteering problem with time windows

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.     

Heuristic approach to allocation of trucks in a transportation system

This paper considers the problem of how luggages should be assign to each truck for the transportation system consists of a depot, a fixed area and two types of luggages, called schedule problem. The main purpose of this paper is to propose a procedure for the problem subject to keep the balance of work loads among truck drivers. The procedure is based on 3 (heuristic) rules for replacing the addresses of each luggage with the ‘conventional address,’ converting size of each luggage into ‘weight’ and introducing a measure to keep the balance of work loads. The procedure consists of three stages according to ‘priority’ of the types of luggages. A case study is presented that demonstrate the practical usefulness of the procedure.     

A bi-objective vehicle routing problem with time windows: A real case in Tenerife

This work is motivated by a real problem posed to the authors by a company in Tenerife, Spain. Given a fleet of vehicles, daily routes have to be designed in order to minimize the total traveled distance while balancing the workload of drivers. This balance has been defined in relation to the length of the routes, regarding to the required time. A bi-objective mixed-integer linear model for the problem is proposed and a solution approach, based on the scatter search metaheuristic, is developed. An extensive computational experience is carried out, using benchmark instances with 25, 50 and 100 customers, to test several components of the proposed method. Comparisons with the exact Pareto fronts for instances up to 25 customers show that the proposed methods obtain good approximations. For comparison purposes, an NSGA-II algorithm has also been implemented. Results obtained on a real case instance are also discussed. In this case, the solution provided by the method proposed in this paper improves the solution implemented by the company.     

A dynamic programming based heuristic for locating stops in public transportation networks

The length of journey towards a bus stop or railway station greatly influences passenger satisfaction and, thus, the utilization of public transport offers. In this context, we investigate the maximum covering location problem in networks (MCLPN) where stops (or stations) are to be located in a given railway or bus network, such that the number of passengers reaching a stop within their particular coverage radius is maximized. Up to now, no specialized solution procedure directly addressing MCLPN exists, instead it is mainly referred to the well-known maximum covering location problem (MCLP), which, however, neglects the underlaying information of the given network structure. This paper exploits the network information, introduces a fast and efficient two-stage dynamic programming based heuristic specifically tailored to MCLPN, and compares it to existing procedures for MCLP. The results show that our heuristic delivers near optimal solutions, i.e., 87% of our test instances are solved to optimality, within a few seconds of computational time.     

公交网络路径规划问题中的一种高效索引方法

TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent Dijkstra为核心算法构建索引,存在两个不足：大量的昂贵的出堆操作拖慢了建立索引的效率以及所求得的路径具有较多的换乘次数。针对这两个不足,提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上做查询,提高效率。TAIL并不是基于图结构,而是以旅程为单位存储公交数据。在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点。为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作,也保留了旅程的完整性。在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少。     

A Coordination-Based Algorithm for Dedicated Destination Vehicle Routing in B2B E-Commerce

This paper proposes a solution to the open vehicle routing problem with time windows (OVRPTW) considering third-party logistics (3PL). For the typical OVRPTW problem, most researchers consider time windows, capacity, routing limitations, vehicle destination, etc. Most researchers who previously investigated this problem assumed the vehicle would not return to the depot, but did not consider its final destination. However, by considering 3PL in the B2B e-commerce, the vehicle is required back to the nearest 3PL location with available space. This paper formulates the problem as a mixed integer linear programming (MILP) model with the objective of minimizing the total travel distance. A coordinate representation particle swarm optimization (CRPSO) algorithm is developed to obtain the best delivery sequencing and the capacity of each vehicle. Results of the computational study show that the proposed method provides solution within a reasonable amount of time. Finally, the result compared to PSO also indicates that the CRPSO is effective.