DaniD Car Rental is developing a replacement policy for each car in its fleet during a 3-year cycle. For each car in the fleet, we assume that DaniD Car Rental must purchase a car at the beginning of each 3-year cycle. At the start of each subsequent year, a decision can be made regarding whether to keep the car or to replace it with a brand new car. Each car has to be in service for at least 1 year. The cost of a brand new car at the beginning of each year, the maintenance costs from year to year, and the trade-in values are shown below. Utilize a shortest path formulation to determine DaniD Car Rental replacement policy.

Year 1 Year 2 Year 3 $25,000 $20,000 $27,000 1,000 1,100 1,200 NA 1.250 1,400 Cost of brand new car at the beginning of year One year maintenance cost for brand new car paid at beginning of year One year maintenance cost for 1-year-old car paid at beginning of year One year maintenance cost for 2-year-old car paid at beginning of year Trade-in value of 1-year- old car at the end of year Trade-in value of 2-year- old car at the end of year Trade-in value of 3-year- old car at the end of year NA NA 1,500 19,000 18,500 18,000 NA 17,000 16,000 NA NA 14000 Year 1 Year 2 Year 3 $25,000 $20,000 $27,000 1,000 1,100 1,200 NA 1.250 1,400 Cost of brand new car at the beginning of year One year maintenance cost for brand new car paid at beginning of year One year maintenance cost for 1-year-old car paid at beginning of year One year maintenance cost for 2-year-old car paid at beginning of year Trade-in value of 1-year- old car at the end of year Trade-in value of 2-year- old car at the end of year Trade-in value of 3-year- old car at the end of year NA NA 1,500 19,000 18,500 18,000 NA 17,000 16,000 NA NA 14000