Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling...Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.展开更多
基金supported by the project of Central University Basic Research Fund(HEUCF150903)the project of the major research task,institute of Policy and Management,Chinese Academy of Sciences(Y201181z01)the National Natural Science Foundation of China(71273072)
文摘Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.
