1、ENRICHING THE TACTICAL NETWORK DESIGN OF EXPRESS SERVICECARRIERS WITH FLEET SCHEDULING CHARACTERISTICS W. J. M. Meuffels H. A. Fleuren F. C. A. M. Cruijssen E. R. van Dam 1 Introduction Express service carriers provide time-guaranteed deliveries of parcels. Directtransport from sender to receiver is
2、 the fastest way of transport but this is in general not cost efficient. Therefore, express carriers operate a network in which parcels ofmany customers are consolidated. Parcels of several senders are consolidated at nodes (in practice called depots, terminals, etc.), transported to other nodes via
3、 theline-haul network and finally delivered to the consignees. We will now briefly describe how the express supply chain is organised. Then a description of networkdesign is given followed by a discussion on fleet scheduling. At the end of this introduction, our research goals are stated. The first
4、node at which a parcel arrives after pickup is called the origin node (ororigin) of the parcel； the node from where the parcel is delivered to the consignee iscalled the destination node (or destination) of the parcel. The transport of parcelsbetween origin node and destination node is called line-h
5、aul. Origin and destinationnode form an od-pair. Cut off times form the connection between the pickup and delivery process and the line-haul process and guarantee the on-time delivery of parcels. That is, all parcels of one service collected in the pickup process have to be processed and loaded into
6、 line-haul vehicles before the collection cut off time of thecorresponding service； the line-haul transport starts afterwards. The line-haul vehicles have to arrive at the destination nodes before the delivery cut off time of the corresponding service. Carriers can use ground or air modes in their l
7、ine-haultransport. Generally, road transport is preferred because of the lower cost involved. Air transport is used to establish services that cannot be offered by ground transport. Considering cost, it is clear that fleet cost dominate in the design of air networks. In road networks, fleet cost is
8、an important cost component though other cost components (like handling cost) are important as well, and the trade off between these cost components determines the final network. In general, strategic and tactical network design discussed in the literature focus on minimisation of the sum of unit tr
9、ansport cost. It is generally assumed that consolidated transport between hub locations benefits from economies of scale such that unit transport cost of inter-hub flows can be discounted. The main restrictions in both strategic and tactical network design are flow conservation and servicecommitment
10、. Flow conservation requires that all flow has to be transported betweennodes； service commitment requires that flows are transported within predefined time limits.After tactical network design, vehicle schedules need to be created such that the flow can be transported. An important aspect of fleet
11、scheduling is the inclusion of waiting times. The first extension on the existing literature concerns the cost function, which inpractice turns out to be more complex than generally seen in the literature. In thelatter, the cost function results from unit transport cost and inter-hub transport isdis
12、counted. However, OKelly and Bryan (1998) claim that the inclusion of anexogenously determined discount applied to all inter-hub arcs regardless of thedifferences in the flows travelling across them, oversimplifies the problem. Theauthors claim that the cost has to be presented by a non-linear funct
13、ion such thatmarginal travel cost decreases as flows increase. The non-linear cost function isafterwards approximated by a piece-wise linear cost function. The cost in our network design incorporates the plainly linear cost function, sincewe explicitly determine vehicle movements. This approach is a
14、pplied to all arcs inthe network, so it is not limited to inter-hub arcs only. The discounting of only interhubarcs was also questioned by Podnar et al. Besides, we improve the reflection of real-world cost made by express carriers bythe inclusion of some other cost components. One of these is vehic
15、le balancing cost.Crainic (2002) describes the need to move empty vehicles because of theimbalances that exist in trade flows that result in discrepancies between vehiclesupply and demand in various zones or nodes in the network. It should be noted that (some of) the cost aspects discussed above are
16、 captured in theliterature on design of air networks. However, to the best of our knowledge, noliterature on the design of road networks has included these cost components in theirmodelling.Express carriers offering next day services face tight time constraints. Theliterature discusses the usage of
17、a cover radius (Kara and Tansel 2003), which is abound on transport time. However, the available time to transport flows depends onthe service definition. The tactical network design model presented in this paperuses cut off times to derive the available time to transport flows. In this way multiple
18、services can be included. However, during network design it is not checked whetherflows can be combined in a truck. This is done in the heuristic that is run afterwards. 2 Related literature This section briefly discusses the literature on the hub network design problem.Recent overviews on hub netwo
19、rk design in express networks are given by Alumurand Kara (2009). Overviews on hub network design in general are given by ReVelleet al. (2008) and Melo et al. (2009). Kuby and Gray (1993) consider the tactical network design in air transportexamining tradeoffs and savings involved with stopovers and
20、 feeders towards asingle air hub location. The authors observed that in real-world practices directflights towards an air hub occur only occasionally: most flights stop over at severalcities along their routes, and often feeder routes with smaller planes transfer loads tolarger planes at intermediat
21、e cities. The tactical hub network design in air transport is further examined by Barnhartand Schneur (1996). Pick up and delivery aircraft routes and schedules are derivedtowards a single hub node. Each aircraft route begins at the hub, visits a set ofdestination nodes followed by an idle period, t
22、hen visits a set of origin nodes beforereturning to the hub. A system that determines aircraft routes, fleet assignments and package routingssimultaneously has been described by Armacost et al. (2004). Like Barnhart andSchneur (1996), pick up and delivery routes towards a single air hub are derivedi
23、ncluding time windows for pick up and delivery. Armacost et al. (2002, 2004) use acomposite variable formulation to solve a comparable model. Lin and Chen (2008) considers the integration of flow routing and fleetscheduling in a network which may contain stopovers and directs. Costcomponents taken i
24、nto account are fixed fleet cost, fleet transportation cost,balancing cost, and location handling cost. Again, fleet routes are derived andeach such route can be performed by one vehicle or aircraft. Compared to theirwork in Lin and Chen (2004), no clustering operation is performed although themodel
25、 will still assign a node location to one hub. However, the hub used forinbound operations can differ from the hub used for outbound operations, thoughall inbound (outbound) flow will use the same route to (from) the hub location.Hub sorts are presented to deal with connectivity issues in order to satisfy servicecommitment. A feasible fleet route plan is determined and afterwards flow routesare derived. 3 Modelling The modelling presented in this section solves the network design and fleetscheduling problem in two steps. First, a tactical network design model is run toderive flow routes. The
