Vehicle Routing Problems With Uncertain Factors

With the rapid development of society economic and e-commerce, there becomes more and more demands for goods transportation, and generates significant volumes of direct-to-customer deliveries. Accordingly, home-delivery services are occupying a larger part of the delivery business, which brings express delivery companies big challenges, that is how to schedule delivery vehicles in order to satisfy customers’ demands in limited time and minimize the operating costs. Delivery issues during the last mile logistics have become important problems to be solved. The study of this paper includes the traveling salesman problem with uncertain factors and the vehicle routing problem with uncertain factors, which is as follows:The traveling salesman problem with stochastic customers is studied. Under the e-commerce environment, a customer has a probability of shopping online every day. Consequently, each customer has a probability of requiring delivery service on a given day. If a logistics company provides delivery service to a customer, it will obtain an associated profit and pay for the corresponding travel cost. In order to maximize its profit, some e-commerce platforms (such as the e-retailer giant in China, Jingdong) set up its own logistics networks, and provide delivery services to some customers by itself and then outsource the transportation services of the remaining customers to carriers that can satisfy the requests at a lower cost. Motivated by this situation, this paper introduces a new routing problem and names it as the probabilistic profitable tour problem (PPTP). It assumes that all customers have a same probability of requiring service. The objective is to find an a priori tour through a subset of customers in order to maximize the expected profit. The delivery man will then follow the order of the a priori tour and visit customers in the tour which have service requests. A non-linear mathematical formulation of this problem is presented, and a genetic algorithm is developed to solve this problem. The computational experiments carried out on small-and moderate-size instances show a good performance of the proposed algorithm.Then, based on the PPTP, we discuss the situation under which customers’ probabilities of requiring a visit are different. We introduce a class of new routing problems and name it as the traveling salesman problems with profit and stochastic customer (TSPPSC). The objective is the simultaneous optimization of the expected collected profits and the expected travel costs. According to the way the two objectives (profits and travel costs) are addressed, TSPPs with stochastic customers are categorized into three sub-problems:the selective travelling salesman problem with stochastic customers (STSPSC), the prize-collecting travelling salesman problem with stochastic customers (PCTSPSC) and the profitable tour problem with stochastic customers (PTPSC). Mathematical formulations are provided for these problems and a simulated annealing hybrid genetic algorithm is proposed to solve one of the sub-problems. Computational experiments conducted on several sets of instances show a good performance of the proposed algorithm.This paper studies the vehicle routing problem with stochastic travel times. Since home-delivery services are occupying a larger part of the delivery business, which brings express delivery companies big challenges. At the meantime, the number of delivery vehicles is increasing in the city center. Therefore, the delivery circumstance in the city center is keeping deteriorating. The vehicles may confront with some uncertain factors during the delivery, such as traffic accidence, traffic jams or bad weather. Under this condition, the travel speed of a delivery vehicle becomes uncertain. For example, the time a vehicle needs to travel a route under traffic jams may be several times of the time a vehicle needs as usual. In this case, the objective of a logistics company is not only to minimize the total travel distance, but also to minimize the total travel time while satisfying consumers’demands. Therefore, this paper relaxes this assumption that the vehicle travel speed is constant and assumes that the travel speed a vehicle travels an arc is stochastic. The travel speed obeys four different functions with respect to departure time and each function has a probability of 25%to be selected. These four functions represent four different traffic conditions. CVRPSTT evaluates delivery routes with four objectives, which are the total travel distance, the total travel time, and the vehicle’balance degree of travel distance and travel time. Since it is a multi-objective problem, the paper defines the dominant relationship of two feasible solutions according to the relationship of their objectives, and then develops an adaptive large neighborhood search heuristic (ALNS) to find the Pareto solutions of the problem. Simulated annealing is used as a local search framework of our ALNS algorithm. The idea of ALNS is to repeatedly improve the initial solution through removal operators and insert operators. If the new solution is better than the current solution, then the new solution is conserved as the initial solution of next iteration. ALNS is applied to solve the single-objective CVRP and the multi-objective CVRP respectively. Computational results of the single-objective CVRP are compared with the results obtained by standard genetic algorithm, which proves the efficiency of our algorithm. By varying the weights of the four objectives, the paper compares and analyses the results of the single-objective CVRP and multi-objective CVRP.