TAILIEUCHUNG - Báo cáo "Algorithm for solution of a routing problem "

In this paper we consider a combinatorial optimization problem that is similar to the bottleneck traveling salesman problem. We show that an optimal tour for this problem is pyramidal tour (1, 3, 5, , n, , 6, 4, 2) or consists of some pyramidal subtours. The above 7methods can be extended to complete bipartite graphs. 1. Problem statement It is well-known that the traveling salesman problem (TSP) is strongly NP-hard (cf. [1], p. 353). But for some special cases of the TSP can be solvable in polynomial time. . | VNU Journal of Science Mathematics - Physics 23 2007 178-182 Algorithm for solution of a routing problem Tran Vu Thieu Pham Xuan Hinh Institute of Mathematics 18 Hoang Quoc Viet Cau Giay Hanoi Vietnam Received 15 November 2006 received in revised form 12 September 2007 Abstract. In this paper we consider a combinatorial optimization problem that is similar to the bottleneck traveling salesman problem. We show that an optimal tour for this problem is pyramidal tour 1 3 5 . n. 6 4 2 or consists of some pyramidal subtours. The above 7methods can be extended to complete bipartite graphs. 1. Problem statement It is well-known that the traveling salesman problem TSP is strongly NP-hard cf. 1 p. 353 . But for some special cases of the TSP can be solvable in polynomial time. This is the case where the distance matrix in the TSP fulfills certain additional conditions . the Monge property Kalmanson matrices the Demidenko conditions or the Supnick conditions cf. 2-4 . In the sequel we will introduce another special case of the TSP which can easily be solvable and show that the optimal tour for this problem is pyramidal tour or consists of some at most three pyramidal subtours. Consider a complete graph G A E with vertex set A a1 a2 . an and edge set E Ax A. Each vertex ai e A has a real number ti i 1 . n called the altitude of vertex ai. We specify vertices ab e A the source and ae e A the sink such that b e e 1 2 . n and tb te. Consider the following problem called Problem A for short Problem A. Find a Hamiltonian path in the graph from ab to ae which visits every vertex exactly once so that to minimize the highest difference between altitudes of any two successive vertices in the path. In other word among permutations n i1 i2 . in of the numbers 1 2 . n with i1 b in e find a permutation so that to minimize the function f n max t. -1. min. 1 k n-1 I k 1 1 I It is easy to see that such a permutation corresponds to a Hamiltonian path in the graph from ab to ae and that the

• Báo cáo khoa học
• routing problem
• Mathematics
• Physics
• Scientific reports
• scientific studies
• natural sciences
• Green open location routing problem considering economic
• Green open location routing costs
• Open Location Routing Problem
• Green Vehicle Routing Problem
• Mixed Integer Linear
• Vehicle Routing Problem
• The electric vehicle routing problem with backhauls
• The electric vehicle routing problem
• Mixed integer linear programming
• Electric vehicle routing problem
• The linehaul route
• Dynamic inventory routing problem
• Policies considering network disruptions
• Inventory routing problem
• Adapting well known instances
• The inventory routing problem
• Imperialist competitive algorithm
• Location routing problem
• Multi objective location routing problem
• Non Dominated Sorting Genetic Algorithm II
• Multi depot location routing problem
• The multi depot electric vehicle location routing problem
• Electric vehicle location routing problem with time windows
• Location routing models
• Extension of the MDVLRP
• Energy support structure
• Multi compartment vehicle routing problem
• General assignment problem
• Fisher and Jaikumar Algorithm Heuristic
• Heterogeneous fleet of vehicle
• Journal of Computer Science and Cybernetics
• Solving min max capacitated vehicle routing problem by local search
• Solving min max capacitated vehicle routing problem
• Solving min max capacitated
• Proposed algorithms compared
• Heuristic algorithm for a multi product four layer
• Multi product four layer capacitated location routing problem
• Adaptive Search Procedure
• The four layer LRP
• Robust approach for solving a vehicle routing problem
• Uncertain service and travel times
• Measures of robustness
• Monte Carlo simulation
• Hybrid heuristic to solve the balanced vehicle routing problem
• The balanced vehicle routing problem with loading constraints
• The Greedy Randomized Adaptive Search Procedure
• Considered simultaneously before
• Added operational constraints
• Metaheuristic algorithm for the multi depot vehicle routing problem
• The multi depot vehicle routing problem with heterogeneous fleet
• High quality solutions
• Obtain high quality solutions
• Hybrid expert system
• Clustering for scheduling and routing problem in courier services
• Ant colony optimization approach for scheduling
• Routing problem in courier services
• Geographically distributed customers
• Variable neighborhood search algorithm
• The green vehicle routing problem
• Variable neighborhood search
• The limit of fuel tank capacity
• Vehicle routing problem for school buses using honey bee algorithm
• School buses using honey bee algorithm
• Presidency school in Bangalore North
• Capacity and cost
• Enhanced heuristic algorithms with a vehicle travel speed model
• Time dependent vehicle routing
• Waste collection problem
• Different initial customer
• Namely current initial solution
• Time Dependent Vehicle Routing Problem
• Generalized multi depot vehicle routing problem
• Replenishment based on LocalSolver
• Constraint conditions and objective functions
• New generation solver
• Depot heterogeneous vehicle routing problem
• Combinatorial optimization
• Efficient transformations
• Generalized combinatorial optimization problems
• Integer programming
• Graph into node sets
• Multiobjective optimization in delivering pharmaceutical products
• Delivering pharmaceutical products
• Disrupted vehicle routing problem
• Improved multiobjective local search
• Hybrid metaheuristic for the time dependent vehicle routing problem
• Hard time windows
• Consequently missed deliveries
• Time dependent travel times
• Hybrid metaheuristic algorithm
• Solving a bi objective mathematical programming model
• Bloodmobiles location routing problem
• Fuzzy multi objective
• Tailored Simulated Annealing
• The bloodmobiles locations
• Multi objective fuzzy
• Solving a multi objective location routing problem
• Infectious waste disposal
• Hybrid goal programming and hybrid genetic algorithm
• Hybrid goal programming
• Hybrid genetic algorithm
• Consolidation centers in city logistics
• The location routing problem
• Urban consolidation Centers
• Fully cooperative scenario
• Facility location decisions
• Consolidate freight delivery services
• Simulated Anealing Algorithm
• Hybrid Vehicle Routing Problem
• Bi objective hybrid vehicle
• Alternative paths and reliability
• Bi objective simulated annealing
• Luận văn Thạc sĩ
• Công nghệ thông tin
• Capacitated vehicle routing problem
• Luận văn thạc Khoa học máy tính
• Khoa học máy tính
• Bài toán định tuyến xe