In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance...In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.展开更多
In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem unde...In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem under path cardinality constraints.Specifically,such a problem formulation captures various types of objectives including proportional fairness,average delay,as well as load balancing.In addition,in order to handle the"unsplittable flows",path cardinality constraints are added,making the resulting optimization problem quite challenging to solve due to intrinsic nonsmoothness and nonconvexity.Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem.However,we provide a novel solution framework based on the linearized alternating direction method of multipliers(LADMM)to split the original problem with coupling terms into several subproblems.We then derive that these subproblems,albeit nonconvex nonsmooth,are actually simple to solve and easy to implement,which can be of independent interest.Under some mild assumptions,we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point.Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various baselines.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.11871213 and 71431004。
文摘In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.
基金supported by the National Natural Science Foundation of China under Grant 11831002。
文摘In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem under path cardinality constraints.Specifically,such a problem formulation captures various types of objectives including proportional fairness,average delay,as well as load balancing.In addition,in order to handle the"unsplittable flows",path cardinality constraints are added,making the resulting optimization problem quite challenging to solve due to intrinsic nonsmoothness and nonconvexity.Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem.However,we provide a novel solution framework based on the linearized alternating direction method of multipliers(LADMM)to split the original problem with coupling terms into several subproblems.We then derive that these subproblems,albeit nonconvex nonsmooth,are actually simple to solve and easy to implement,which can be of independent interest.Under some mild assumptions,we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point.Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various baselines.
