http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
장병만 한국경영과학회 1998 經營 科學 Vol.15 No.2
This paper presents a new algorithm for the K Shortest Paths Problem which is developed with a Double Shortest Arborescence and an inward arc breaking method. A Double Shortest Arborescence is made from merging a forward shortest arborescence and a backward one with Dijkstra algorithm, and shows us information about each shorter path to traverse each arc. Then K shorter paths are selected in ascending order of the length of each short path to traverse each arc, and some paths of the K shorter paths need to be replaced with some hidden shorter paths in order to get the optimal paths. And if the cross nodes which have more than 2 inward arcs are found at least three times in K shorter path, the first inward arc of the cross node is broken and a new shorter path is exposed. If this exposed path is shorter than the Kth shorter path, the exposed path replaces the Kth shorter path. This procedure is repeated until the cross nodes are not found in K shorter paths, and then the K shortest paths problem is solved exactly. This algorithm are computed with complexity O(n^3) and especially O(n^2) in the case K=3.
Column Generation법에 의한 관광 버스 배차 방법
장병만 서울産業大學校 1987 논문집 Vol.25 No.1
This paper presents an optimization based heuristic algorithm for a tour bus scheduling problem where buses consist of various kinds of sightseeing and communication services. First this algorithm transforms the problem into a vehicle routing problem on whose nodes denote trips and arcs denote connections between trips. Second a greedy heuristic routing technique is applied to find a good feasible bus-route set. Then the greedy feasible solution is improved by the simplex method using column generation technique. The algorithm provides a better near-optimal solution which gives much reductions in the total tour distance and the number of tour buses.
장병만 서울産業大學校 1990 논문집 Vol.31 No.1
The public Vehicle Routing Problem(PVRP) is to find the minimum total cost routes of M or less Public-Vehicles to traverse the required arcs(streets) at least once, and return to their starting depot on a directed network. In this paper, first, a mathematical model is formulated as minimal cost flow model with illegal subtour elimination constraints, and with the fixed cost and routing cost as an objective function. Second, an efficient branch and bound algorithm is developed to obtain an exact solution. A subproblem in this method is a minimal cost flow problem relaxing illegal subtour elimination constraints. The branching strategy is a variable dichotomy method according to the entering nonrequired arcs which are candidates to enter into an illegal subtour. To accelerate the fathoming process, a tighter lower bound of a entering nonrequired arcs. Computational results based on randomly generated networks report that the developed algorithm is efficient.
첨단도로 교통체계 차량안내용의 시간종속복수 최단 경로해법
장병만 한국경영과학회 1998 한국경영과학회 학술대회논문집 Vol.- No.1
In a dynamic route guidance, an algorithm is needed that calculates the time - dependent shortest paths to a given destination node for every time step a given time horizon in a network with time dependent link cost. This approach can try to handle simultaneously both the shortest time paths (user optimum) and traffic assignment (system optimum ). It discretizes the horizon of interest into small time intervals. In every time step, the link costs are calculated with the sigmoid function, which is inversely propositional to traffic conjestion and density approximately. And K =3 shortest time paths algorithm is developed with a Double Shortest Arborescence which provides three exposed shortest path between the source and the sink with time complexity O ( n^2 ). T his Double Shortest Arborescence is consisted of a forward shortest arborescence and a backward one with the Dijkstra algorithm. All pair of K =3 shortest time path algorithm are made with repeating the K =3 shortest path algorithm between each node and are computed with complexity O (n^4).
다품종 복수공장 생산에서의 생산 분배 및 수송 계획 문제연구
장병만 한국경영과학회 1993 한국경영과학회 학술대회논문집 Vol.- No.1
This paper presents a model and a heuristic procedure to design production planning and transportation scheduling systems of critical items, components and products on the basis of material requirement planning concept and transportation planning model. These systems are stemmed from a multi-site multi-product provided to validate the heuristic procedure developed.