Disclosed is a method for setting vehicle routing to minimize greenhouse gas emission. The method for setting vehicle routing to minimize greenhouse gas emission can include: a first step for setting arbitrary routing so that each of k vehicles (k is a natural number), for which the maximum capacity and maximum travel time are set, starts from the departure point, passes through N nodes (N is a natural number) only once, and then returns to the departure point; a second step for determining the existence of at least one first routing, in which the maximum capacity is violated, and at least one second routing, in which the maximum travel time is violated, among the set routings; a third step for increasing the first Lagrangian multiplier of a term related to the capacity of the vehicle among the terms of an objective function using Lagrangian Relaxation by a times (a is a real number greater than 1) if the first routing exists; a fourth step for increasing the second Lagrangian multiplier of a term related to the travel time of the vehicle among the terms of the objective function using Lagrangian Relaxation by b times (b is a real number greater than 1) if the second routing exists; a fifth step for modifying the routings using a k-opt algorithm; and a step for repeating the third step to the fifth step until the first routing and the second routing do not exist in the routings modified by carrying out the fifth step.

    온실가스 배출량을 최소화하는 차량 경로 설정 방법이 개시된다. 상기 온실가스 배출량을 최소화하는 차량 경로 설정 방법은, 최대 용량 및 최대 운행시간이 설정되어 있는 k 대(k는 자연수)의 차량 각각이 출발지에서 출발하여 N(N은 자연수)개의 노드를 한번만 경유한 후 다시 출발지로 돌아오도록 임의의 경로를 설정하는 제 1 단계, 상기 설정된 경로들 중 상기 최대 용량이 위반되는 적어도 하나의 제 1 경로 및 상기 최대 운행시간이 위반되는 적어도 하나의 제 2 경로의 존재 여부를 판단하는 제 2 단계, 상기 제 1 경로가 존재하는 경우 라그랑지안 완화법을 이용한 목적함수의 항들 중 차량의 용량에 관련된 항의 제 1 라그랑지안 승수를 a배(a는 1 보다 큰 실수)로 증가시키는 제 3 단계, 상기 제 2 경로가 존재하는 경우 상기 라그랑지안 완화법을 이용한 목적함수의 항들 중 차량의 운행시간에 관련된 항의 제 2 라그랑지안 승수를 b배(b는 1 보다 큰 실수)로 증가시키는 제 4 단계, k-opt 알고리즘을 이용하여 상기 경로를 수정하는 제 5 단계 및 상기 제 5 단계를 수행하여 수정된 경로들 중 상기 제 1 경로 및 상기 제 2 경로가 존재하지 않을 때까지 상기 제 3 단계 내지 제 5 단계를 반복하여 수행하는 단계를 포함할 수 있다.


    Access

    Download


    Export, share and cite



    Title :

    Method for setting vehicle routing to minimize greenhouse gas emission


    Additional title:

    온실가스 배출량을 최소화하는 차량 경로 설정 방법


    Contributors:
    GYU MIN LEE (author)

    Publication date :

    2019-03-08


    Type of media :

    Patent


    Type of material :

    Electronic Resource


    Language :

    Korean


    Classification :

    IPC:    G01C Messen von Entfernungen, Höhen, Neigungen oder Richtungen , MEASURING DISTANCES, LEVELS OR BEARINGS / B60W CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION , Gemeinsame Steuerung oder Regelung von Fahrzeug-Unteraggregaten verschiedenen Typs oder verschiedener Funktion / G06F ELECTRIC DIGITAL DATA PROCESSING , Elektrische digitale Datenverarbeitung




    Vehicle routing problem modelling to minimize a number of vehicle by considering heterogenous fleet vehicle

    Arvianto, Ary / Perkasa, Dwi Satria / Budiawan, Wiwik et al. | IEEE | 2015


    Routing UAVs to Minimize the Chance of Detection

    Malik, A. / Batta, R. / Karwan, M. H. et al. | British Library Conference Proceedings | 2004


    A distributed multipath routing algorithm to minimize congestion

    Xin, Guo / Jun, Zhang / Tao, Zhang | IEEE | 2009