시간 제약을 가지는 차량 경로 스케줄링 문제해결을 위한 기회시간 반영 하이브리드 휴리스틱

유영훈(Young-Hoon Yu),차상진(Sang-Jin Cha),조근식(Geun-Sik Jo) 한국지능정보시스템학회 2009 지능정보연구 Vol.15 No.3

This paper proposes the hybrid heuristic method to apply the opportunity time to solve the vehicle routing and scheduling problem with time constraints(VRSPTW). The opportunity time indicates the idle time which remains after the vehicle performs the unloading service required by each customer's node. In this proposed heuristic, we add the constraints to VRSPTW model for the opportunity time. We also obtain the initial solution by applying the cost evaluation function to the insertion strategy considering the opportunity time. In addition, we improve the former result by applying the opportunity time to the tabu search strategy by swapping the customer's node. Finally, we suggest the construction strategies of initial routing which can efficiently acquire the nearest optimal solution from various types of data in terms of geographical condition, scheduling horizon and vehicle capacity. Our experiment show that our heuristic can get the nearest optimal solution more efficiently than the Solomon’s I1 heuristic.

패턴 빔을 이용한 BGA 단차 측정

신상훈,유영훈,Shin, Sang-Hoon,Yu, Young-Hun 한국광학회 2009 한국광학회지 Vol.20 No.6

본 연구에서는 패턴 빔을 이용하여 표면이 거친 물체의 단차를 비접촉 방식으로 측정 하는 방법에 대하여 연구하였다. 본 연구에 사용된 방법은 장치가 매우 간단하고 스페클 노이지가 영상에 미치는 영향이 작아 재현성 면에서 매우 우수하였다. 특히 기준면에 문양이 없는 경우에는 기존의 자동 초점 측정 장치로는 측정하기 어려우나, 본 연구 방법에 의해 측정이 가능함을 보였다. 그리고 측정 시간이 매우 짧고 재현성이 좋으며 장치가 간단하여 산업 현장에서 응용하기 적절한 방법이다. We describe a simple method to obtain an optical sectioning in a conventional wide-field microscope by projecting a single spatial frequency grid pattern onto the object. Using a patterned beam, we have measured the height of BGA with a rough surface that provide the coherence noise. The configuration of the height measurement system using pattern beam is simple. The image acquired by this system is not depend on the coherence noises. This system is also applicable to the sample reference plan that has no pattern on ground. The reappearance and accuracy are outstanding and applicable to many industrial optical metrology.

차량 경로 스케줄링 문제 해결을 위한 개미 군집 최적화 휴리스틱

홍명덕,유영훈,조근식,Hong, Myung-Duk,Yu, Young-Hoon,Jo, Geun-Sik 한국정보처리학회 2010 정보처리학회논문지B Vol.17 No.5

차량 경로 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)는 여러 고객의 시간 제약과 요구량을 만족시키면서 최소 이동 비용을 가지는 경로를 구성하는 문제이다. 이 문제는 NP-Hard 문제이기 때문에 해를 산출하는데 시간이 오래 걸린다. 본 연구는 VRSPTW를 빠른 시간 내에 최근사해를 구하기 위한 멀티 비용 함수(Multi Cost Function)를 갖는 개미 군집 최적화(Ant Colony Optimization)을 이용한 휴리스틱을 제안하였다. 멀티 비용 함수는 각 개미가 다음 고객 노드로 이동하기 위해 비용을 평가할 때 거리, 요구량, 각도, 시간제약에 대해 서로 다른 가중치를 반영하여 우수한 초기 경로를 구할 수 있도록 한다. 본 연구의 실험결과에서 제안된 휴리스틱이 Solomon I1 휴리스틱과 기회시간이 반영된 하이브리드 휴리스틱보다 효율적으로 최근사 해를 얻을 수 있음을 보였다. The Vehicle Routing and Scheduling Problem with Time Windows(VRSPTW) is to establish a delivery route of minimum cost satisfying the time constraints and capacity demands of many customers. The VRSPTW takes a long time to generate a solution because this is a NP-hard problem. To generate the nearest optimal solution within a reasonable time, we propose the heuristic by using an ACO(Ant Colony Optimization) with multi-cost functions. The multi-cost functions can generate a feasible initial-route by applying various weight values, such as distance, demand, angle and time window, to the cost factors when each ant evaluates the cost to move to the next customer node. Our experimental results show that our heuristic can generate the nearest optimal solution more efficiently than Solomon I1 heuristic or Hybrid heuristic applied by the opportunity time.

디지털 홀로그래피 현미경과 위상 펼침을 이용한 3차원 측정

조형준,김두철,유영훈,정원기,신상훈,Cho, Hyung-Jin,Kim, Doo-Chul,Yu, Young-Hun,Jung, Won-Gi,Shin, Sang-Hoon 한국광학회 2006 한국광학회지 Vol.17 No.4

마이크로미터 이하 물체의 2차원 및 영상과 3차원 영상을 동시에 측정하기 위하여 off-axis 투과형 디지털 홀로그래피 현미경을 구성하였다. 그리고 3차원 영상을 얻기 위하여 Mask-Cut 위상 펼침 알고리즘을 사용하였다. 측정 결과 2차원 상에는 0.8 $\mu$m 이하의 문양도 측정할 수 있음을 확인하였다. 그리고 마이크로미터 이하 물체의 2차원 영상과 3차원 영상을 동시에 측정 할 수 있음을 확인하였다. We have reconstructed 3-dimensional images by using the digital holographic microscope and the Mask-cut phase unwrapping algorithm. Off-axis holograms recorded with a magnified image of the microscopic object lens and reference beam are numerically reconstructed in amplitude and phase image by the Fresnel diffraction approximation. We have simultaneously reconstructed 2-dimensional and 3-dimensional images of the sub-micrometer objects.

복소공액 홀로그램을 이용한 디지털 홀로그래피 연구

신상훈,김두철,유영훈,Shin, Sang-Hoon,Kim, Doo-Cheol,Yu, Young-Hun 한국광학회 2010 한국광학회지 Vol.21 No.4

디지털 홀로그래피에서 재생상을 재생할때 복소공액 홀로그램을 도입하여 위상 왜곡과 잡음이 제거된 재생 영상을 얻는 방법에 대하여 연구하였다. 일반적으로 디지털 홀로그램은 시료의 위상 정보 외에 위상 정보에 겹쳐져 있어 잡음으로 작용하는 허상, DC항 뿐만 아니라 측정 시스템의 위상 왜곡 현상도 모두 포함되어 기록된다. 기록된 홀로그램에서 시료의 위상 정보만을 분리하여 이를 재생하면 질 좋은 위상 재생상을 얻을 수 있다. 본 연구에서는 복소공액 홀로그램을 이용하면 off-axis 및 in-line 홀로그래피에서 위상왜곡과 측정시스템이 가지고 있는 잡음을 제거 할 수 있음을 실험적으로 확인하였다. In this paper we have applied phase conjugated holographyto DHM (digital holography microscopy) to remove phase aberration and noise. Generally,digital holographyincludes the phase information of the object, phase aberration terms introduced by the measurement system and noise terms (DC term and twin images). These aberrations and noise terms decrease the quality of the reconstructed phase image. We could obtain a conjugated hologram which includes only phase information of object. Experimentally we show that distortion of image and aberration of phase in a measurement system are removed using the conjugation hologram.

굴절률 차이와 디지털 홀로그래피를 이용한 큰 단차측정

조형준,김두철,유영훈,신상훈,이혁수,Cho, Hyung-Jun,Kim, Doo-Cheol,Yu, Young-Hun,Shin, Sang-Hoon,Lee, Hyuk-Soo 한국광학회 2009 한국광학회지 Vol.20 No.2

디지털 홀로그램과 굴절률 차이를 이용하여 사용된 광원의 파장보다 큰 단차를 측정하는 연구를 하였다. 위상차를 측정하여 단차를 측정하는 방식에서는 위상차가 $2{\pi}$보다 큰 경우에는 원리상 단차를 구하기 어렵다. 이를 보완하기 위하여 굴절률 차이를 이용하여 인위적으로 광경로차를 줄여 파장보다 큰 단차를 측정할 수 있는 디지털 홀로그래피 시스템을 구성하였고, 실험적으로 파장의 약 3배 이상의 단차를 측정하였다. Digital holography and refractive index difference are used to measure a high aspect ratio's patterns. When interference fringes are very closely spaced, the phase data containing high frequencies where $2{\pi}$ ambiguities cannot be resolved. In this technique, the optical path difference is decreased by decreasing the refractive index difference. As a result, we solve the $2{pi}$ ambiguities. Also, this technique is applicable to measure the refractive index if the shape of the sample is known.

이중푸리에변환을 이용한 2 파장 디지털 홀로그래픽 연구

신상훈,정원기,유영훈,Shin, Sang-Hoon,Jung, Won-Ki,Yu, Young-Hun 한국광학회 2010 한국광학회지 Vol.21 No.3

디지털 홀로그램을 이용하여 상을 재생 할 때 재생상의 크기는 재생거리와 파장의 함수이다. 이러한 재생거리와 파장 의존성을 제거하기 위하여 이중푸리에변환법이 제안되었고, 이중푸리에변환을 이용하면 일정 크기의 재생상을 얻을 수 있다. 일반적으로 사용된 광원의 파장보다 큰 단차의 높낮이 측정은 단일파장 디지털 홀로그래픽 방식으로 측정이 가능하지 않기 때문에 2 파장홀로그래피가 제안되었는데, 두 파장에서 얻어진 각각의 재생상의 크기가 같아야 하는 제약이 있다. 본 연구에서는 투과 및 반사형 2 파장 디지털 홀로그래픽 현미경을 이용하여 각각의 파장별로 홀로그램을 촬영하고 이중푸리에변환을 이용하여 재생함으로써 두개의 파장에서 얻어진 재생상의 크기를 같게 만들어 주는 과정 없이 단차를 가진 샘플의 3차원 높낮이 측정을 할 수 있었다. The size of a reconstructed image depends on the reconstruction distance and wavelength. The double fourier transform method is proposed to eliminate the dependence on the reconstruction distance and wavelength. We can get a fixed reconstructed image size by using the double fourier transform method. Two wavelength digital holography is proposed to measure the step height, which is larger than a single wavelength. The two image size of different wavelength holograms should be the same in order to apply two wavelength digital holography. We use two wavelength digital holography and double fourier transforms to measure the step height. The measured data were reasonable and we found that the double fourier transform is useful in two wavelength digital holography.

디지털 홀로그래피 현미경에서의 스캐닝 방법을 이용한 영차회절광 제거

조형준,김두철,유영훈,신상훈,Cho, Hyung-Jun,Kim, Doo-Chul,Yu, Young-Hun,Shin, Sang-Hoon 한국광학회 2006 한국광학회지 Vol.17 No.4

디지털 홀로그램에서 영상 재현 시 영차 회절광에 의한 잡음으로 신호대 잡음비가 좋은 영상을 구현하기 어렵다. 이와 같은 이유로 디지털 홀로그램이 여러 분야에 응용되는 것이 어렵다. 영차 회절광 제거를 위하여 많은 노력이 이루어져 왔다. 본 연구에서는 영차 회절광의 영향을 줄이기 위한 홀로그램 데이터를 스캐닝 방법으로 획득하여 수치적 처리를 통하여 영상을 재현하는 실험 연구를 하였다. 그 결과 본 연구에 사용된 방법이 영차 회절광의 효과를 줄이면서 해상도도 유지 할 수 있는 방법임을 알았다. A fundamental problem in digital holography is the presence of zero-order noise in the reconstruction process, which decreases the signal to noise ratio(SNR). For many applications, that reduction of SNR makes digital holography impractical, so a great number of approaches have been tested in order to overcome such a problem. In this paper we use the scanning method to suppress the zero-order diffraction noise and the interference noise between object beams. We demonstrate that it is possible to increase the image quality with the scanning method.

VRPSPD 해결을 위한 위치기반의 실시간 재경로 탐색 휴리스틱

차상진,이기성,유영훈,조근식,Cha, Sang-Jin,Lee, Kee-Sung,Yu, Young-Hoon,Jo, Geun-Sik 한국공간정보학회 2010 한국공간정보학회지 Vol.18 No.3

The vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) is a variant of the vehicle routing problem (VRP) that customers require simultaneously a pick-up and delivery service. The main objective of VRPSPD is to minimize a cost of routes satisfying many constraints. Traditional VRPSPD have been dealt with a static environment. The static environment means that a routing data and plan cannot be changed. For example, it is difficult to change a vehicle's routing plan so that a vehicle serves the pick-up demands of new customers during the delivery service. Therefore, traditional approach is not suitable for dynamic environments. To solve this problem, we propose a novel approach for finding efficient routes using a real-time re-routing heuristics based on the Location Based Service (LBS). Our re-routing heuristics can generate a new route for vehicle that satisfies a new customer's demand considering the current geographic location of a vehicle. Experimental results show that our methodology can reduce the traveling cost of vehicles comparing with other previous methods. 일반적인 Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries (VRPSPD)는 배송과 수거가 동시에 발생하는 문제를 고려한 차량경로 문제이며, 차량의 운행 거리등의 비용을 최소화하는 것을 결정하는 문제이다. 그러나 기존의 VRPSPD는 이미 차량이 출발하기 전에 경로가 정해져 있어서 차량 운행 중 발생하는 고객의 수거 요청을 기존의 경로에 효율적으로 추가하여 서비스하기가 어렵다. 따라서 본 논문에서는 이러한 문제를 위치기반의 서비스를 이용하여 이동 중인 차량의 위치정보를 파악하고 이를 바탕으로 실시간 재경로 탐색을 통해 해결하는 휴리스틱을 제안한다. 그리고 실험을 통해 기존의 방식과 비교하여 차량을 운행하는데 소요되는 비용을 줄이는 결과를 보였다.

한정 용량 차량 경로 탐색 문제에서 이분 시드 검출 법에 의한 발견적 해법

고준택(Jun-Taek Ko),유영훈(Young-Hoon Yu),조근식(Geun-Sik Jo) 한국지능정보시스템학회 2009 지능정보연구 Vol.15 No.1

The Capacitated Vehicle Routing Problem (CVRP) is the problem that the vehicles stationed at central depot are to be optimally routed to supply customers with demands, satisfying vehicle capacity constraints. The CVRP is the NP-hard as it is a natural generalization of the Traveling Salesman Problem (TSP). In this article, we propose the heuristic algorithm, called the bisection seed detection method, to solve the CVRP. The algorithm is composed of 3-phases. In the first phase, we work out the initial cluster using the improved sweep algorithm. In the next phase, we choose a seed node in each initial cluster by using the bisection seed detection method, and we compose the rout with the nearest node from each seed. At this phase, we compute the regret value to decide the list of priorities for the node assignment. In the final phase, we improve the route result by using the tabu search and exchange algorithm. We compared our heuristic with different heuristics such as the Clark-Wright heuristic and the genetic algorithm. The result of proposed heuristic show that our algorithm can get the nearest optimal value within the shortest execution time comparatively.