排序方式: 共有14条查询结果,搜索用时 15 毫秒
1.
2.
Yannis?MarinakisEmail author Athanasios?Migdalas Panos?M.?Pardalos 《Computational Optimization and Applications》2005,32(3):231-257
In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure
(GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution
of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The
local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested
on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results
were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson. 相似文献
3.
Hoang Tuy Saied Ghannadan Athanasios Migdalas Peter Värbrand 《Mathematical Programming》1996,72(3):229-258
We show that the production-transportation problem involving an arbitrary fixed number of factories with concave production
cost is solvable in strongly polynomial time. The algorithm is based on a parametric approach which takes full advantage of
the specific structure of the problem: monotonicity of the objective function along certain directions, small proportion of
nonlinear variables and combinatorial properties implied by transportation constraints. 相似文献
4.
A novel approach to Bilevel nonlinear programming 总被引:3,自引:3,他引:0
Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex
optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional
programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the
monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into
a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound
method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.
相似文献
5.
Hoang Tuy Saied Ghannadan Athanasios Migdalas Peter Värbrand 《Journal of Global Optimization》1995,6(2):135-151
We prove that the Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs can be solved by an algorithm requiring a number of elementary operations and a number of evaluations of the nonlinear cost functions which are both bounded by polynomials inr, n, m, wherer is the number of nodes,n is the number of arcs andm the number of sinks in the network.On leave from Institute of Mathematics, P.O. Box 631, Bo Ho, Hanoi, Vietnam. 相似文献
6.
A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm 总被引:2,自引:0,他引:2
Yannis Marinakis Athanasios Migdalas Panos M. Pardalos 《Journal of Global Optimization》2007,38(4):555-580
The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems
and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together
with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem
of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility
of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles
will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision
maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment
is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of
customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population
and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory
results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances
proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the
quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature
for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational
time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact
that the Expanding Neighborhood Search Strategy is used. 相似文献
7.
A global optimization approach for the linear two-level program 总被引:4,自引:0,他引:4
Linear two-level programming deals with optimization problems in which the constraint region is implicity determined by another optimization problem. Mathematical programs of this type arise in connection with policy problems to which the Stackelberg leader-follower game is applicable. In this paper, the linear two-level programming problem is restated as a global optimization problem and a new solution method based on this approach is developed. The most important feature of this new method is that it attempts to take full advantage of the structure in the constraints using some recent global optimization techniques. A small example is solved in order to illustrate the approach.The paper was completed while this author was visiting the Department of Mathematics of Linköping University. 相似文献
8.
Jun Pei Xinbao Liu Panos M. Pardalos Athanasios Migdalas Shanlin Yang 《Journal of Global Optimization》2017,67(1-2):251-262
This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively. 相似文献
9.
Jun Pei Xinbao Liu Panos M. Pardalos Kai Li Wenjuan Fan Athanasios Migdalas 《Optimization Letters》2017,11(7):1257-1271
This article considers the single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. The objective of this problem is to make the decision of batching jobs and sequencing batches to minimize the makespan. To solve the problem, three cases of machine non-availability periods are considered, and the structural properties of the optimal solution are derived for each case. Based on these structural properties, an optimization algorithm is developed and an example is proposed to illustrate this algorithm. 相似文献
10.
The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most
significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers
need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable.
In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood
Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP
has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm
is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP
algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number
of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm
gives a new best solution. 相似文献