FULL-TRUCK-LOAD ASSIGNMENT AND ROUT

FULL-TRUCK-LOAD ASSIGNMENT AND ROUTE
PLANNING IN DETERMINISTIC AND STOCHASTIC
ENVIRONMENTS1
Hossein Jula*
, Maged Dessouky**, Petros Ioannou*§
, and Randolph Hall**
* Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089-2562
** Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089-0193
§ Corresponding author: Email: [e-mail], Tel: [phone]
Abstract: The full-truck-load route planning and scheduling with time appointment system falls
in the class of Traveling Salesman Problem with Time Windows (TSPTW). In this paper, methods
for improving the scheduling of intermodal trucks in deterministic and stochastic environments,
where ISO containers need to be transferred between marine terminals, intermodal facilities, and
end customers are investigated. The objective is to reduce empty miles, and to improve customer
service. Computational experiments are used to demonstrate the efficiency of the proposed
methods.
1. INTRODUCTION
The substantial increase in international volume of cargo arriving at U.S. ports together with the
growth in the national freight have introduced congestion at many traffic networks and led to new
dynamics in surface transportation. Worldwide container trade is growing at a 9.5% annual rate, and
the U.S. growth rate is around 6% (Vickerman 1998). Every major port is anticipated to at least double
its cargo by 2020 (Ryan 1998). As a consequence, truck traffic in the vicinity of the nation’s ports is
likely to grow substantially, leading to increased roadway congestion, and delays for both ordinary
drivers and for the import and export of goods.
In today’s trucking industry, there is a lot of discussion about the appointment window system (which
will be called time window, hereafter) to manage the flow of trucks in traffic networks and at
customers’ locations. This system requires that freight carriers deliver/pick-up their cargo within a

1
This work is supported in part by the National Science Foundation under grant DMI-0127965, and in part by
METRANS located at the University of Southern California and the California State University at Long Beach. The
contents of this paper reflect the views of the authors who are responsible for the facts and the accuracy of the data
presented herein.
2003 NSF Design, Service and Manufacturing Grantees and Research Conference Proceedings
Edited by R.G. Reddy, The University of Alabama, Tuscaloosa, AL 35487, USA; Pages 2957-2971.
specified time period due to the commitments made to the end customers, and due to the limited
availability of certain resources at terminals.
In this paper methods are investigated to improve the scheduling of trucks in deterministic and
stochastic environments, where ISO containers need to be transferred between marine terminals,
intermodal facilities, and end customers. The containers need to be delivered/picked up within a
specified time period. The objective is to reduce empty miles, and to improve customer service. The
problems studied fall in the class of full-truck-load vehicle planning, routing and scheduling, which can
be modeled by the Traveling Salesman Problem with Time Windows (TSPTW) (Savelsbergh and Sol
1995, Jula et al. 2002).
It should be noted that the TSPTW problem is an interesting special case of the Vehicle Routing
Problem with Time Windows (VRPTW) in which the capacity constraints are relaxed. Recently the
VRPTW, and a variety of its practical applications have been the subject of a wide body of research
(Golden and Assad 1988, Laporte 1992, Desrochers et al. 1992, Ball et al. 1995, Dumas et al. 1995,
Kohl et al. 1999). In VRPTW a number of vehicles, each with a given capacity, is located at a single
depot and must serve a number of geographically dispersed customers. Each customer has a given
demand and must be served within a specified time window. The objective is to minimize the total
cost of travel (Desrochers et al. 1988).
In this paper, we study the full-truck-load routing, planning and scheduling both in the deterministic
and stochastic networks. For the deterministic network, the multi-vehicle TSPTW is considered, and
the following three methodologies are developed and compared.
a. An exact method based on Dynamic Programming (DP),
b. A hybrid methodology consisting of dynamic programming in conjunction with genetic
algorithms (GA), and
c. A heuristic insertion method.
For the stochastic environment, we develop a methodology to address the existing non-linearity
formed by hard time window. Furthermore, we propose an approximate solution method for nonstationary
stochastic TSPTW with random travel and service times.
2. DETERMINISTIC ENVIRONMENT
2.1. Problem Description
Let G=(ND,A) be a graph with node set ND={o,d,N} and arc set A={(i,j)| i,jÎND}. The nodes {o}
and {d} represent the single depot (origin-depot and destination-depot), and N={1,2,…,n} is the set
of customers. To each arc (i,j)ÎA, a cost cij and a duration of time tij are associated representing the
cost and time of traveling between nodes i and j, respectively. In addition, to each node iÎND a
service time si and a time window [ , ] ai bi
are associated. The service time si
is the duration of time for
a vehicle to be served at node i, and ai and bi are the earliest and latest time to visit node i,
respectively. An arc (i,j)ÎA is feasible iff i i ij bj a + s + t £ . Let V be the set of vehicles v. A route in
the graph G is defined as assigning a set of nodes r
v
={o, wv
1,wv
2,…,wv
k,d} to vehicle v such that each
arc in r
v
belongs to A, and the time that service begins at node jÎr
v
is within the time window of that
node.
Let's also define: x
v
ij=1 if arc (i,j)ÎA is traveled by vehicle v and is in the optimal path. x
v
ij=0
otherwise. T
v
i is the time when service begins at node i by vehicle v.
The m-TSPTW can be formulated as follows:
Constraints ( 1b ) require that only one vehicle visit each node in N. Constraints ( 1c ) ensure that at
most |V| number of vehicles are used. To fix the number of vehicles, the inequality should be replaced
by equality. Constraints ( 1d ) guarantee that the number of vehicles leaving node j is the same as the
number of vehicles entering the node. Therefore, constraints ( 1b ) to ( 1d ) together enforce that at
most |V| number of vehicles visit all nodes in N only once. Constraints ( 1e ) enforce the time
feasibility condition on consecutive nodes. Constraints ( 1f ) specify the time window constraints at
each node. Constraints ( 1g ) require that each vehicle shall be used less than a certain number of hours
per day, and finally constraints ( 1h ) are the binary constraints.
2.2. Proposed Solution Methods for m-TSPTW
It should be noted that in contrast to the relation between the TSP and the m-TSP (e.g., see Reinelt
(1994)), the m-TSPTW cannot be transformed into an equivalent TSPTW. In the following, we have
developed three methodologies to solve the m-TSPTW.
2.2.1. Exact method for m-TSPTW
A two-phase Dynamic Programming (DP) based method is proposed for solving the m-TSPTW. The
method is an extension of the algorithm used for the TSPTW and proposed in Dumas et al. (1995).
Partial paths, however, which cannot be extended to other nodes, will not be eliminated, as it may be
on the optimum set of solutions. Moreover, at each node tests are conducted to ensure the reachability
of the depot according to the constraint ( 1g ). The outcome of the first phase will be sets of feasible
solutions. The sets, then, will be fed to another DP algorithm in order to find a set of routes with
minimum total cost which covers all nodes.
Min å å vÎV i j ÎA
v
ij ij c x
( , )
( 1a )
Subject to å å Î Î È
=
v V j N d
v
ij x
{ }
1 " iÎN ( 1b )
ååÎ Î
£
v V j N
v
xoj V " iÎN, vÎV ( 1c )
å å Î È Î È
- =
{ } { }
0
j N d j N o
v
ji
v
ij x x " i,jÎND, vÎV ( 1d )
( + + - ) £ 0
v
i ij j
v
i
v
xij T s t T " i,jÎND, vÎV ( 1e )
i
v
i i
a £ T £ b " iÎND, vÎV ( 1f )
T T T
v
o
v
d - £ " vÎV ( 1g )
Î{0,1}
v
xij " (i,j)ÎA, vÎV ( 1h )
Phase One: We require that the triangular inequality holds for both the travel costs and the travel
times between each two nodes of the graph G. That is, for any i,j,kÎND, we have cik£cij+cjk and
tik£tij+tjk. Let SÍN be an unordered set of visited nodes, iÎS be the last visited node by vehicle v (i.e.,
on path v); and t be the time at which service begins at node i. Associated to each state (S,i,t), defined
above, is a cost denoted by F(S,i,t) and defined as the least cost with minimum spanned time of a path
starting at node {o}ÎND passing through every node of S exactly once and ending at node i. Note
that, there are several paths that visit set S and end at node i. Among them, we choose the one with
minimum cost and minimum spanned time (see the state elimination test 2, below). Let also fr(S)ÎN
be the first node in set S. The starting time of set S is denoted by tfr(S) and is defined as tfr(S)=max(ao,
afr(s) – so – to,fr(s)). This time indicates the earliest possible vehicle dispatching time from the depot such
that no waiting time is necessary at node fr(S).
In order to reduce the computational time, two types of elimination tests are performed: arc
elimination, and state elimination.
1) Arc elimination tests: These tests are performed before and during running the DP algorithm.
a. Arc elimination before running the algorithm. Let EAT(i,j) be the earliest arrival time at node j
from node i. EAT(i,j) is defined as follows:
i i ij EAT(i, j) = a + s + t ( 2 )
Let also BEFORE(j) be the set of all nodes that should be visited before node j, and is defined
as follows:
BEFORE( j) = {k Î N D EAT( j, k) > bk} ( 3 )
Nodes which can not be covered by set BEFORE(j) will be added to set FORBID(j).
b. Arc elimination during running the algorithm. Given state (S,i,t), ai£t£bi, the time to visit
node jÎN after node i is t+si+tij. The reachability time of the depot, {d}ÎND, after visiting
node j is deno

ผลลัพธ์ (ไทย) 1:

กำหนดเต็มรถบรรทุกโหลดและกระบวนการผลิตการวางแผน ใน DETERMINISTIC สโทแคสติกENVIRONMENTS1Hossein จุฬา *, Maged Dessouky ** Petros Ioannou * แท้และแรนโดล์ฟฮอลล์ *** ภาควิชาวิศวกรรมไฟฟ้า มหาวิทยาลัยเซาเทิร์นแคลิฟอร์เนีย Los Angeles, CA 90089-2562** ภาคอุตสาหกรรมและระบบวิศวกรรม มหาวิทยาลัยเซาเทิร์นแคลิฟอร์เนีย Los Angeles, CA 90089-0193ผู้เขียนที่สอดคล้องกันของแท้: อีเมล์: [e-mail] โทร: 4452 740 (213)บทคัดย่อ: โหลดรถบรรทุกเต็มกระบวนการผลิตการวางแผน และกำหนดเวลานัดหมายระบบอยู่ในคลาสของปัญหา Traveling ขายด้วยเวลา Windows (TSPTW) ในเอกสารนี้ วิธีการสำหรับการปรับปรุงการจัดกำหนดการของรถบรรทุก intermodal deterministic และสโทแคสติกสภาพแวดล้อมภาชนะบรรจุ ISO ต้องโอนย้ายระหว่างเทอร์มินัลทางทะเล intermodal สิ่งอำนวยความสะดวก และสุดท้ายลูกค้าจะตรวจสอบ วัตถุประสงค์คือ ลดเปล่าไมล์ และปรับปรุงลูกค้าบริการ ใช้คำนวณการทดลองแสดงให้เห็นถึงประสิทธิภาพของการนำเสนอวิธี1. บทนำระดับนานาชาติสหรัฐอเมริกาขนส่งสินค้าเพิ่มพบพอร์ตร่วมกับการเจริญเติบโตในการขนส่งแห่งชาติได้นำแออัดในเครือข่ายรับส่งข้อมูลมาก และนำไปใหม่dynamics ผิวขนส่ง ค้าคอนเทนเนอร์ทั่วโลกมีการเติบโตในอัตราปี 9.5% และอัตราการเติบโตของสหรัฐฯ เป็นประมาณ 6% (Vickerman 1998) คาดทุกพอร์ตหลักสองน้อยการขนส่งสินค้า โดย 2020 (ไรอัน 1998) ผล จราจรรถบรรทุกอีกพอร์ตของประเทศเป็นแนวโน้มที่จะเติบโตมาก นำแออัดถนนเพิ่มขึ้น และความล่าช้าสำหรับทั้งธรรมดาโปรแกรมควบคุม และการนำเข้าและส่งออกสินค้าในวันนี้รถขนส่งอุตสาหกรรม มีจำนวนมากของการอภิปรายเกี่ยวกับระบบหน้าต่างการนัดหมาย (ซึ่งจะเรียกหน้าต่างเวลา โดย) เพื่อจัดการการไหลของรถบรรทุก ในเครือข่ายการจราจร และที่สถานของลูกค้า ระบบนี้ต้องการการขนส่งผู้ขน ส่ง/pick-ค่าขนส่งสินค้าของตนภายใน1 งานนี้ได้รับการสนับสนุนบางส่วน โดยมูลนิธิวิทยาศาสตร์แห่งชาติภาย ใต้ทุน DMI 0127965 และบางส่วนโดยMETRANS อยู่มหาวิทยาลัยเซาเทิร์นแคลิฟอร์เนียและมหาวิทยาลัยแห่งรัฐแคลิฟอร์เนียที่ลองบีช ที่เนื้อหาของเอกสารนี้สะท้อนมุมมองของผู้เขียนที่รับผิดชอบสำหรับข้อเท็จจริงและความถูกต้องของข้อมูลนำเสนอนี้ออกแบบ 2003 NSF บริการ และการผลิต Grantees และตอนประชุมวิจัยแก้ไข โดย R.G. เรดดี มหาวิทยาลัยอาลาบาม่า Tuscaloosa อัล 35487 สหรัฐ อเมริกา 2957-2971 หน้าเวลาที่ระบุเนื่อง จากข้อผูกมัดทำให้การสิ้นสุด และเนื่อง จากการจำกัดความพร้อมของทรัพยากรบางอย่างที่เทอร์มินัลในเอกสารนี้ ตรวจสอบวิธีการปรับปรุงการจัดกำหนดการของรถบรรทุกใน deterministic และสภาพแวดล้อมแบบเฟ้นสุ่ม ที่บรรจุ ISO ต้องการโอนย้ายระหว่างเทอร์มินัลทางทะเลสิ่งอำนวยความสะดวก intermodal และลูกค้าสิ้นสุด ภาชนะบรรจุต้องมีส่ง/รับในการรอบระยะเวลาที่ระบุ วัตถุประสงค์คือ ลดเปล่าไมล์ และปรับปรุงการบริการลูกค้า ที่ปัญหาเรียนอยู่ในคลาสของรถโหลดรถบรรทุกเต็มวางแผน สายงานการผลิต และการจัด กำหนดการ ซึ่งสามารถสร้างแบบจำลองปัญหา Traveling ขายด้วยเวลา Windows (TSPTW) (Savelsbergh และโซล1995 จุฬา et al. 2002)ควรสังเกตว่า ปัญหา TSPTW กรณีพิเศษน่าสนใจของเส้นทางรถปัญหากับเวลา Windows (VRPTW) ซึ่งจะผ่อนคลายข้อจำกัดกำลังการผลิต เมื่อเร็ว ๆ นี้VRPTW และความหลากหลายของการปฏิบัติมีหัวข้อของเนื้อหาวิจัยกว้าง(ทอง และ Assad 1988, 1992, Desrochers et al. 1992 บอลร้อยเอ็ด al. 1995 ดูมาส et al. 1995, Laporteโครงการร้อยเอ็ด al. 1999) จำนวนยานพาหนะ VRPTW มีการกำหนดกำลังการผลิต อยู่ที่เดียวdepot และต้องรองรับจำนวนลูกค้ากระจัดกระจายกันทางภูมิศาสตร์ ลูกค้าแต่ละรายมีการกำหนดความต้องการ และต้องเสิร์ฟภายในหน้าต่างเวลาที่ระบุ วัตถุประสงค์คือเพื่อ ลดยอดรวมต้นทุนการเดินทาง (Desrochers et al. 1988)ในเอกสารนี้ เราเรียนเต็มรถบรรทุกโหลดสายงานการผลิต การวางแผน และการวางแผนทั้งในแบบ deterministicและเครือข่ายแบบเฟ้นสุ่ม สำหรับเครือข่าย deterministic, TSPTW รถหลายถือ และวิธีสามต่อไปนี้จะพัฒนา และเปรียบเทียบa. เป็นวิธีที่แน่นอนตามในแบบไดนามิกโปรแกรม (DP),b. A hybrid methodology consisting of dynamic programming in conjunction with geneticalgorithms (GA), andc. A heuristic insertion method.For the stochastic environment, we develop a methodology to address the existing non-linearityformed by hard time window. Furthermore, we propose an approximate solution method for nonstationarystochastic TSPTW with random travel and service times.2. DETERMINISTIC ENVIRONMENT2.1. Problem DescriptionLet G=(ND,A) be a graph with node set ND={o,d,N} and arc set A={(i,j)| i,jÎND}. The nodes {o}and {d} represent the single depot (origin-depot and destination-depot), and N={1,2,…,n} is the setof customers. To each arc (i,j)ÎA, a cost cij and a duration of time tij are associated representing thecost and time of traveling between nodes i and j, respectively. In addition, to each node iÎND aservice time si and a time window [ , ] ai biare associated. The service time siis the duration of time fora vehicle to be served at node i, and ai and bi are the earliest and latest time to visit node i,respectively. An arc (i,j)ÎA is feasible iff i i ij bj a + s + t £ . Let V be the set of vehicles v. A route inthe graph G is defined as assigning a set of nodes rv={o, wv1,wv2,…,wvk,d} to vehicle v such that eacharc in rv belongs to A, and the time that service begins at node jÎrvis within the time window of thatnode. Let's also define: xvij=1 if arc (i,j)ÎA is traveled by vehicle v and is in the optimal path. xvij แค = 0มิฉะนั้น Tvฉันเป็นเวลาเมื่อบริการเริ่มต้นที่โหนดฉัน โดยยานพาหนะ vM-TSPTW สามารถจะถูกกำหนดเป็นดังนี้:ชมรถเดียวที่แต่ละโหนดในตอนเหนือจำกัด (1c) ให้แน่ใจว่าที่ต้องใช้ข้อจำกัด (1b)มากที่สุด | V| จำนวนยานพาหนะที่ใช้ เมื่อต้องการแก้ไขหมายเลขของยานพาหนะ ความไม่เท่าเทียมกันควรแทนด้วยความเสมอภาคกัน ข้อจำกัด (1d) รับประกันว่า จำนวนรถยนต์ที่ออกจากโหนด j เป็นเหมือนการจำนวนยานพาหนะที่ป้อนโหน ดังนั้น ข้อจำกัด (1b) (1d) ร่วมกันบังคับที่มากที่สุด | V| จำนวนยานพาหนะเที่ยวโหนทั้งหมดใน N เพียงครั้งเดียว เวลาบังคับใช้ข้อจำกัด (1e)เงื่อนไขความเป็นไปได้บนโหนดที่ติดกัน ข้อจำกัดของหน้าต่างเวลาที่ระบุข้อจำกัด (1f)แต่ละโหน ข้อจำกัด (1g) ต้องว่า พาหนะจะใช้น้อยกว่าจำนวนของชั่วโมงต่อวัน และสุดท้ายข้อจำกัด (1h) มีข้อจำกัดแบบไบนารี2.2 เสนอวิธีแก้ปัญหาสำหรับ m TSPTWก็ควรจดบันทึกซึ่งตรงกันข้ามกับความสัมพันธ์ระหว่าง m-ช้อนชาและช้อนชา (เช่น ดู Reinelt(1994)), ไม่มีเปลี่ยน m TSPTW เป็น TSPTW เทียบเท่า ในต่อไปนี้พัฒนา 3 วิธีแก้ m TSPTW2.2.1 m-TSPTW วิธีแน่นอนมีเสนอ two-phase ไดนามิกโปรแกรม (DP) ตามวิธีการแก้ไข m TSPTW ที่วิธีเป็นการขยายอัลกอริทึมที่ใช้สำหรับ TSPTW และ al. เสนอในดูมาสร้อยเอ็ด (1995)บางส่วนเส้นทาง อย่างไรก็ตาม ที่ไม่สามารถขยายไปยังโหน จะไม่มีตัด มันอาจจะon the optimum set of solutions. Moreover, at each node tests are conducted to ensure the reachabilityof the depot according to the constraint ( 1g ). The outcome of the first phase will be sets of feasiblesolutions. The sets, then, will be fed to another DP algorithm in order to find a set of routes withminimum total cost which covers all nodes.Min å å vÎV i j ÎAvij ij c x( , )( 1a )Subject to å å Î Î È=v V j N dvij x{ }1 " iÎN ( 1b )ååΠΣv V j Nvxoj V " iÎN, vÎV ( 1c )å å Î È Î È- ={ } { }0j N d j N ovjivij x x " i,jÎND, vÎV ( 1d )( + + - ) £ 0vi ij jvivxij T s t T " i,jÎND, vÎV ( 1e )ivi ia £ T £ b " iÎND, vÎV ( 1f )T T Tvovd - £ " vÎV ( 1g )Î{0,1}vxij " (i,j)ÎA, vÎV ( 1h )Phase One: We require that the triangular inequality holds for both the travel costs and the traveltimes between each two nodes of the graph G. That is, for any i,j,kÎND, we have cik£cij+cjk andtik£tij+tjk. Let SÍN be an unordered set of visited nodes, iÎS be the last visited node by vehicle v (i.e.,on path v); and t be the time at which service begins at node i. Associated to each state (S,i,t), definedabove, is a cost denoted by F(S,i,t) and defined as the least cost with minimum spanned time of a pathstarting at node {o}ÎND passing through every node of S exactly once and ending at node i. Notethat, there are several paths that visit set S and end at node i. Among them, we choose the one withminimum cost and minimum spanned time (see the state elimination test 2, below). Let also fr(S)ÎN
be the first node in set S. The starting time of set S is denoted by tfr(S) and is defined as tfr(S)=max(ao,
afr(s) – so – to,fr(s)). This time indicates the earliest possible vehicle dispatching time from the depot such
that no waiting time is necessary at node fr(S).
In order to reduce the computational time, two types of elimination tests are performed: arc
elimination, and state elimination.
1) Arc elimination tests: These tests are performed before and during running the DP algorithm.
a. Arc elimination before running the algorithm. Let EAT(i,j) be the earliest arrival time at node j
from node i. EAT(i,j) is defined as follows:
i i ij EAT(i, j) = a + s + t ( 2 )
Let also BEFORE(j) be the set of all nodes that should be visited before node j, and is defined
as follows:
BEFORE( j) = {k Î N D EAT( j, k) > bk} ( 3 )
Nodes which can not be covered by set BEFORE(j) will be added to set FORBID(j).
b. Arc elimination during running the algorithm. Given state (S,i,t), ai£t£bi, the time to visit
node jÎN after node i is t+si+tij. The reachability time of the depot, {d}ÎND, after visiting
node j is deno

ผลลัพธ์ (ไทย) 2:

FULL-TRUCK-โหลดมอบหมายและวิถีทาง
ในการวางแผนและกำหนด Stochastic
ENVIRONMENTS1
โฮส Jula *
, Maged Dessouky ** Petros Ioannou * §
และ Randolph ฮอลล์ **
* ภาควิชาวิศวกรรมไฟฟ้า, University of Southern California, Los Angeles, CA 90089- 2562
** กรมโรงงานอุตสาหกรรมและวิศวกรรมระบบ University of Southern California, Los Angeles, CA 90089-0193
§ผู้รับผิดชอบ: อีเมล์: [e-mail] โทรศัพท์: [phone]
บทคัดย่อ: เต็ม truck- การวางแผนเส้นทางการโหลดและการกำหนดเวลาที่มีระบบการแต่งตั้งครั้งที่ตกอยู่
ในชั้นเรียนของปัญหาการเดินทางพนักงานขายกับเวลาของ Windows (TSPTW) ในบทความนี้วิธีการ
สำหรับการปรับปรุงการจัดตารางเวลาของรถบรรทุกขนส่งในสภาพแวดล้อมที่กำหนดและสุ่ม,
ISO ที่ภาชนะบรรจุจะต้องมีการโอนย้ายระหว่างขั้วทางทะเลสิ่งอำนวยความสะดวกการขนส่งและ
ลูกค้าปลายจะถูกตรวจสอบ โดยมีวัตถุประสงค์เพื่อลดไมล์ว่างเปล่าและลูกค้าในการปรับปรุง
บริการ การทดลองคอมพิวเตอร์ที่ใช้ในการแสดงให้เห็นถึงประสิทธิภาพของการเสนอ
วิธีการ.
1 บทนำ
เพิ่มขึ้นมากในต่างประเทศปริมาณของสินค้าที่เดินทางมาถึงที่ท่าเรือสหรัฐพร้อมกับ
การเจริญเติบโตในการขนส่งสินค้าแห่งชาติได้นำความแออัดของการจราจรในเครือข่ายจำนวนมากและนำไปสู่การใหม่
ในการเปลี่ยนแปลงพื้นผิวการขนส่ง ภาชนะค้าทั่วโลกมีการเติบโตที่ 9.5% ต่อปีและ
อัตราการเจริญเติบโตของสหรัฐอยู่ที่ประมาณ 6% (Vickerman 1998) ทุกเมืองท่าสำคัญคาดว่าจะไม่น้อยกว่าสองเท่า
ของการขนส่งสินค้าในปี 2020 (ไรอัน 1998) เป็นผลให้การจราจรรถบรรทุกในบริเวณใกล้เคียงของพอร์ตของประเทศที่มี
แนวโน้มที่จะเติบโตอย่างมีนัยสำคัญที่นำไปสู่ความแออัดของถนนที่เพิ่มขึ้นและความล่าช้าในการสามัญทั้ง
คนขับและสำหรับการนำเข้าและการส่งออกสินค้า.
ในอุตสาหกรรมรถบรรทุกของวันนี้มีเป็นจำนวนมาก อภิปรายเกี่ยวกับระบบหน้าต่างได้รับการแต่งตั้ง (ซึ่ง
จะถูกเรียกว่าหน้าต่างเวลาต่อจากนี้) ในการจัดการการไหลของรถบรรทุกในเครือข่ายการจราจรและที่
สถานที่ของลูกค้า ระบบนี้จะต้องมีการให้บริการขนส่งสินค้าที่ส่ง / รับจากการขนส่งสินค้าของพวกเขาภายใน1 งานนี้ได้รับการสนับสนุนในส่วนของมูลนิธิวิทยาศาสตร์แห่งชาติภายใต้ทุน DMI-0127965 และในส่วนของMetrans ตั้งอยู่ที่ University of Southern California และมหาวิทยาลัยแห่งรัฐแคลิฟอร์เนีย ที่ลองบีช เนื้อหาของบทความนี้สะท้อนให้เห็นถึงมุมมองของผู้เขียนที่มีความรับผิดชอบในข้อเท็จจริงและความถูกต้องของข้อมูลที่นำเสนอในที่นี้. 2003 NSF การออกแบบและการผลิตบริการและผู้รับดำเนินการประชุมวิจัยแก้ไขโดย RG เรดดี้มหาวิทยาลัยอลาบา, ทัสคาลู, AL 35487 สหรัฐอเมริกา; หน้า 2957-2971. ระยะเวลาที่กำหนดเนื่องจากภาระผูกพันที่เกิดขึ้นกับลูกค้าปลายและเนื่องจากการ จำกัดพร้อมของทรัพยากรบางอย่างที่อาคาร. วิธีการในบทความนี้จะถูกตรวจสอบเพื่อปรับปรุงการจัดตารางเวลาของรถบรรทุกในการกำหนดและสภาพแวดล้อมที่สุ่มที่ ISO ภาชนะที่จะต้องมีการโอนย้ายระหว่างขั้วทางทะเลสิ่งอำนวยความสะดวกการขนส่งและปลายลูกค้า ภาชนะที่จะต้องมีการส่งมอบ / หยิบขึ้นมาภายในระยะเวลาที่กำหนด โดยมีวัตถุประสงค์เพื่อลดไมล์ว่างเปล่าและปรับปรุงการบริการลูกค้า ปัญหาการศึกษาฤดูใบไม้ร่วงในชั้นเรียนของเต็มรถบรรทุกรถโหลดการวางแผนเส้นทางและการกำหนดเวลาที่สามารถจะสร้างแบบจำลองโดยพนักงานขายที่เดินทางปัญหากับ Time Windows (TSPTW) (Savelsbergh และโซลปี 1995 Jula et al. 2002). ควร จะตั้งข้อสังเกตว่าปัญหา TSPTW เป็นกรณีพิเศษที่น่าสนใจของการกำหนดเส้นทางยานพาหนะปัญหากับ Time Windows (VRPTW) ซึ่ง จำกัด กำลังการผลิตจะผ่อนคลาย เมื่อเร็ว ๆ นี้VRPTW และความหลากหลายของการใช้งานจริงที่ได้รับเรื่องของลำตัวกว้างของการวิจัย(โกลเด้นและอัสซาด 1988 พอร์ต 1992 Desrochers et al. 1992, บอล et al. 1995 มัส et al. 1995 เอตตา al. 1999) ใน VRPTW จำนวนของยานพาหนะแต่ละคนมีความสามารถในการรับตั้งอยู่ที่เดียวที่สถานีรถไฟและต้องให้บริการจำนวนของลูกค้าที่กระจายตัวทางภูมิศาสตร์ ลูกค้าแต่ละคนมีที่กำหนดความต้องการและต้องทำหน้าที่ภายในหน้าต่างเวลาที่กำหนด โดยมีวัตถุประสงค์เพื่อลดการรวมค่าใช้จ่ายของการเดินทาง (Desrochers et al. 1988). ในบทความนี้เราศึกษาเส้นทางเต็มรถบรรทุกโหลดการวางแผนและจัดตารางการทั้งในกำหนดเครือข่ายและสุ่ม สำหรับเครือข่ายที่กำหนด, TSPTW หลายยานพาหนะมีการพิจารณาและวิธีการดังต่อไปนี้ได้รับการพัฒนาและเปรียบเทียบ. วิธีการที่แน่นอนขึ้นอยู่กับการเขียนโปรแกรมแบบไดนามิก (DP) ข วิธีการไฮบริดซึ่งประกอบด้วยการเขียนโปรแกรมแบบไดนามิกในทางพันธุกรรมร่วมกับอัลกอริทึม (GA) และค วิธีการแก้ปัญหาการแทรก. สำหรับสภาพแวดล้อมการสุ่มเราพัฒนาวิธีการที่จะอยู่เป็นเส้นตรงที่ไม่ได้มีอยู่ที่เกิดขึ้นจากหน้าต่างเวลาที่ยากลำบาก นอกจากนี้เรายังนำเสนอวิธีการแก้ปัญหาโดยประมาณสำหรับไม่คงที่TSPTW สุ่มกับการเดินทางครั้งสุ่มและบริการ. 2 สิ่งแวดล้อมที่กำหนด2.1 คำอธิบายปัญหาให้ g = (ND,) เป็นกราฟที่มีโหนดตั้ง ND = {O, D, N} และโค้งตั้ง = {(ฉัน j) | i, Jind} โหนด {O} และ {d} เป็นตัวแทนของสถานีเดียว (แหล่งกำเนิดสถานีรถไฟและสถานีปลายทาง) และไม่มีข้อความ = {1,2, ... , n} คือชุดของลูกค้า โค้งแต่ละ (ฉัน j) IA, CIJ ค่าใช้จ่ายและระยะเวลาของการ TIJ เวลามีความเกี่ยวข้องเป็นตัวแทนของค่าใช้จ่ายและเวลาในการเดินทางระหว่างโหนด i และ j ตามลำดับ นอกจากนี้ในการแต่ละโหนด IInd เวลาการให้บริการศรีและหน้าต่างเวลา [] ai สองมีความเกี่ยวข้อง เวลาการให้บริการ si เป็นระยะเวลาสำหรับรถที่จะให้บริการที่โหนด i และ ai และสองเป็นเวลาที่เร็วและล่าสุดที่จะเยี่ยมชมโหนด i, ตามลำดับ โค้ง (ฉัน j) IA เป็นไปได้ก็ต่อ ii เจ bj + S + T ปอนด์ ให้ V เป็นชุดของยานพาหนะ v. เส้นทางในกราฟ G ถูกกำหนดให้เป็นกำหนดชุดของโหนดอาวี= {o, WV 1, WV 2, ... , wv k, d} รถโวลต์ดังกล่าวว่าแต่ละโค้งใน อาร์วีเป็นที่และเวลาที่ให้บริการเริ่มต้นที่โหนดjÎr โวลต์เป็นภายในหน้าต่างเวลาที่โหนด. Let 's ยังกำหนด: x วีเจ = 1 ถ้าโค้ง (ฉัน j) IA จะเดินทางโดยรถโวลต์และอยู่ใน เส้นทางที่ดีที่สุด x วีเจ = 0 เป็นอย่างอื่น T โวฉันคือเวลาที่ให้บริการเริ่มต้นที่โหนดฉันโดยใช้ยานพาหนะ v. ม TSPTW ได้สูตรดังนี้จำกัด (1b) จำเป็นต้องใช้ว่ามีเพียงหนึ่งคันเข้าชมแต่ละโหนดในเอ็น จำกัด (1c) ให้แน่ใจว่าที่มากที่สุด | V | จำนวนของยานพาหนะที่ใช้ใน ในการแก้ไขปัญหาจำนวนของยานพาหนะ, ความไม่เท่าเทียมกันควรจะถูกแทนที่โดยเท่าเทียมกัน จำกัด (1 วัน) รับประกันว่าจำนวนของยานพาหนะออกจากเจโหนดเป็นเช่นเดียวกับจำนวนของยานพาหนะเข้าโหนด ดังนั้นการ จำกัด (1b) ถึง (1 วัน) พร้อมบังคับว่าในที่สุด | V | จำนวนของยานพาหนะเยี่ยมชมโหนดทั้งหมดในไม่มีข้อความเพียงครั้งเดียว จำกัด (1e) เวลาบังคับใช้สภาพความเป็นไปได้บนโหนติดต่อกัน จำกัด (1F) ระบุข้อ จำกัด หน้าต่างเวลาที่แต่ละโหนด จำกัด (1 กรัม) จำเป็นต้องให้รถแต่ละคันจะถูกใช้น้อยกว่าจำนวนหนึ่งชั่วโมงต่อวันและในที่สุดก็ จำกัด (1 ชั่วโมง) เป็นข้อ จำกัด ไบนารี. 2.2 วิธีการเสนอโซลูชั่นม TSPTW มันควรจะตั้งข้อสังเกตว่าในทางตรงกันข้ามกับความสัมพันธ์ระหว่าง TSP และ M-TSP (เช่นเห็น Reinelt (1994)) ม TSPTW ไม่สามารถเปลี่ยนเป็น TSPTW เทียบเท่า ในต่อไปนี้เราได้พัฒนาสามวิธีการที่จะแก้ปัญหาของ m-TSPTW. 2.2.1 วิธีการที่แน่นอนสำหรับม TSPTW สองเฟสการเขียนโปรแกรมแบบไดนามิก (DP) วิธีการตามเสนอในการแก้ม TSPTW วิธีการเป็นส่วนขยายของอัลกอริทึมที่ใช้สำหรับ TSPTW และนำเสนอในมัสเอตอัล (1995). เส้นทางบางส่วน แต่ที่ไม่สามารถขยายไปยังโหนดอื่น ๆ จะไม่ถูกตัดออกเป็นมันอาจจะอยู่ในชุดที่ดีที่สุดของการแก้ปัญหา นอกจากนี้ในแต่ละโหนดการทดสอบจะดำเนินการเพื่อให้แน่ใจว่าการเชื่อมของสถานีให้เป็นไปตามข้อ จำกัด (1 กรัม) ผลที่ได้จากขั้นตอนแรกจะเป็นชุดที่เป็นไปได้การแก้ปัญหา ชุดแล้วจะถูกป้อนไปยังอีกขั้นตอนวิธี DP เพื่อหาชุดของเส้นทางที่มีค่าใช้จ่ายรวมต่ำสุดซึ่งครอบคลุมทุกโหนด. มินเป็นไอวีเจ IA วีเจเจ CX () (1a) เรื่องที่ฉัน ÎÈ = โวลต์วีญงเอ็นวีเจ x } { 1 "Iin (1b) AAI Î £ วีวีเจเอ็นวีxoj วี "Iin, VIV (1c) åฉันÈÎÈ - = {} {} 0 ญ ไม่มีดีเจเอ็น o วีจีวีเจ XX "ฉัน Jind, VIV (1 วัน) (+ -) £ 0 โวลต์ผม IJ เจโวฉันv xij เซนต์ T T "ฉัน Jind, VIV (1e) ฉันv ii ปอนด์ T £ข "IInd, VIV (1F) TTT วีโอวีd - £ "ไอวี (1 กรัม) i {0,1} วีxij "(ฉัน j) IA, VIV (1 ชั่วโมง) ขั้นตอนที่หนึ่ง: เราต้องการให้เป็นรูปสามเหลี่ยม ความไม่เท่าเทียมกันถือทั้งค่าใช้จ่ายในการเดินทางและการเดินทางครั้งระหว่างสองโหนดของกราฟกรัมนั่นคือสำหรับผมใด ๆ เจชนิดเรามี CIK £ CIJ + CJK และtik £ TIJ + TJK. ให้บาปจะเรียงลำดับ ชุดของโหนดเข้าเยี่ยมชม IIS เป็นโหนดเข้าเยี่ยมชมที่ผ่านมาโดยยานพาหนะวี (เช่นบนเส้นทางโวลต์) และเสื้อจะเป็นเวลาที่ให้บริการเริ่มต้นที่โหนดฉันที่เกี่ยวข้องแต่ละรัฐ (s, i, t) ที่กำหนดไว้. ข้างต้น เป็นค่าใช้จ่ายที่แสดงโดย F (S, i, t) และกำหนดให้เป็นค่าใช้จ่ายน้อยขั้นต่ำทอดเวลาของเส้นทางเริ่มต้นที่โหนด {O} Ind ผ่านโหนดของ S ทุกครั้งว่าและสิ้นสุดที่โหนดฉัน หมายเหตุว่ามีหลายเส้นทางที่เยี่ยมชมตั้ง S และสิ้นสุดที่โหนดฉัน ในหมู่พวกเขาเราเลือกหนึ่งที่มีค่าใช้จ่ายต่ำสุดและต่ำสุดที่เวลาทอด (ดูการกำจัดรัฐทดสอบที่ 2 ด้านล่าง) ยังให้เ (S) ในโหนดเป็นครั้งแรกในชุดเอสเวลาเริ่มต้นของการตั้งค่า S จะเขียนแทนด้วย TFR (S) และถูกกำหนดให้เป็น TFR (S) = max (อ่าว, AFR (s) - เพื่อ - เพื่อ, เ (s)) ในครั้งนี้แสดงให้เห็นรถที่เร็วที่สุดเยี่ยงอย่างเวลาจากสถานีดังกล่าวว่าไม่มีเวลาที่รอคอยเป็นสิ่งที่จำเป็นที่เโหนด (S). เพื่อที่จะลดเวลาในการคำนวณสองประเภทของการทดสอบจะดำเนินการกำจัด: อาร์. การกำจัดและการกำจัดของรัฐ1 ) Arc การทดสอบการกำจัด:. ทดสอบเหล่านี้จะดำเนินการก่อนและระหว่างการทำงานขั้นตอนวิธี DP การกำจัดอาร์ก่อนที่จะใช้อัลกอริทึม ให้กิน (ฉัน j) เป็นครั้งที่เดินทางมาถึงเร็วญโหนดจากโหนดฉัน กิน (ฉัน j) ถูกกำหนดให้ดังต่อไปนี้: ii เจกิน (ฉัน j) = + S + T (2) ให้ยังก่อน (ญ) เป็นชุดของโหนดทั้งหมดที่ควรจะเข้าเยี่ยมชมก่อนที่จะเจโหนดและเป็น ที่กำหนดไว้ดังต่อไปนี้ก่อน (ญ) = {k Î ND EAT (ญ, k)> BK} (3) โหนดที่ไม่สามารถได้รับการคุ้มครองโดยการตั้งค่าก่อน (ญ) จะถูกเพิ่มในการตั้งห้าม (ญ). ข การกำจัดอาร์ในช่วงขั้นตอนวิธีการทำงาน รัฐน (S, i, t) ai £เสื้อ£สองเวลาในการเยี่ยมชมจินหลังจากโหนดโหนดฉันคือ T + + si TIJ เวลาการเชื่อมของสถานี {d} Ind หลังจากไปเจโหนดเป็น Deno

ผลลัพธ์ (ไทย) 3:

การขนส่งแบบเต็มคันรถกำหนดและวางแผนเส้นทาง


และ deterministic Stochastic ใน environments1 Hossein จูลา *
, maged dessouky * * ใกล้ ioannou * §
และแรนดอล์ฟ Hall * *
* ภาควิชาวิศวกรรมไฟฟ้า มหาวิทยาลัยของภาคใต้ของรัฐแคลิฟอร์เนีย , Los Angeles , CA 90089-2562
* * ภาควิชาวิศวกรรมอุตสาหการและระบบ มหาวิทยาลัยแคลิฟอร์เนีย ทางตอนใต้ของ Los Angeles , CA 90089-0193
§สอดคล้องกัน ผู้เขียน : อีเมล์ : [e-mail] , โทร : ( 213 ) 740 4452
บทคัดย่อ : การวางแผนเส้นทางรถบรรทุกโหลดเต็มและจัดตารางระบบนัดหมายเวลาตก
ในชั้นเรียนของการเดินทางปัญหาพนักงานขายกับ Windows เวลา ( tsptw ) ในกระดาษนี้ วิธีการ
สำหรับการปรับปรุงจัดการขนส่งรถบรรทุกในเชิงกำหนดสภาพแวดล้อมและ Stochastic
ที่ ISO บรรจุต้องถูกโอนย้ายระหว่างทะเลขั้ว สิ่งอำนวยความสะดวกการขนส่งและ
ลูกค้าสิ้นสุดสัญญาณ โดยมีวัตถุประสงค์เพื่อลดไมล์ว่างและเพื่อปรับปรุงการบริการลูกค้า

การทดลอง การคำนวณจะใช้เพื่อแสดงให้เห็นถึงประสิทธิภาพของวิธีเสนอ
.
1 บทนำ
เพิ่มขึ้นอย่างมากในปริมาณของสินค้ามาถึงสหรัฐอเมริการะหว่างประเทศพอร์ตพร้อมกับ
การเจริญเติบโตในการขนส่งแห่งชาติได้แนะนำเครือข่ายการจราจรและความแออัดที่มากมายทำให้พลวัตใหม่
ในการขนส่งพื้นผิว ค้าคอนเทนเนอร์ทั่วโลกจะเติบโตในอัตราปีละ 9.5 % และอัตราการเจริญเติบโตของสหรัฐ
ประมาณ 6% ( วีเคอร์เมิ่น 2541 ) ทุกพอร์ตหลักคาดว่าจะอย่างน้อยสองครั้ง
ของสินค้าโดย 2020 ( ไรอัน ปี 2541 ) อย่างไรก็ดีการจราจรรถบรรทุก ในบริเวณท่าเรือของประเทศ
มีแนวโน้มการเติบโตเพิ่มขึ้นอย่างมาก ทำให้เกิดความแออัดและล่าช้าสำหรับถนน , ทั้งธรรมดา
ไดรเวอร์สำหรับการนำเข้าและส่งออกสินค้า
ในอุตสาหกรรมรถบรรทุกในวันนี้ มีมากของการอภิปรายเกี่ยวกับระบบหน้าต่างนัด ( ซึ่ง
จะเรียกหน้าต่าง เวลา