Route and network: CAT Previous Year Questions
Q. 1 Instructions
Every day a widget supplier supplies widgets from the warehouse (W) to four locations – Ahmednagar (A), Bikrampore (B), Chitrachak (C), and Deccan Park (D). The daily demand for widgets in each location is uncertain and independent of each other. Demands and corresponding probability values (in parenthesis) are given against each location (A, B, C, and D) in the figure below. For example, there is a 40% chance that the demand in Ahmednagar will be 50 units and a 60% chance that the demand will be 70 units. The lines in the figure connecting the locations and warehouse represent two-way roads connecting those places with the distances (in km) shown beside the line. The distances in both the directions along a road are equal. For example, the road from Ahmednagar to Bikrampore and the road from Bikrampore to Ahmednagar are both 6 km long.
Every day the supplier gets the information about the demand values of the four locations and creates the travel route that starts from the warehouse and ends at a location after visiting all the locations exactly once. While making the route plan, the supplier goes to the locations in decreasing order of demand. If there is a tie for the choice of the next location, the supplier will go to the location closest to the current location. Also, while creating the route, the supplier can either follow the direct path (if available) from one location to another or can take the path via the warehouse. If both paths are available (direct and via warehouse), the supplier will choose the path with minimum distance.
If the last location visited is Ahmednagar, then what is the total distance covered in the route (in km)?
Check Solution
Ans: 35
Key considerations for route planning:
1. The route commences at the distribution hub and concludes at a designated point after visiting every site precisely one time.
2. When formulating the route, the vendor prioritizes sites based on demand in descending order. In instances of equal demand, proximity to the current location takes precedence.
3. During route construction, the vendor has two options for travel between sites: a direct connection (if established) or a route passing through the distribution hub. The option minimizing travel distance is chosen.
In the problem statement, it is specified that the final destination is site A. The demand at all other locations must exceed that of A. Consequently, A’s demand cannot be 70 units, leaving it at 50 units.
Site D has a demand of either 30 or 50 units. This indicates D must be visited before a site with a demand of 50 units or more. The site visited immediately preceding D must have a demand of at least 50 units. Site B has a demand of 60 units. Site C’s demand is higher than B’s, so C cannot be the site visited before D.
Therefore, the sequence of visits is C – B – D – A.
Travel segments and distances:
* Distribution hub to C: 12 km
* C to B: 4 km
* B to D: 12 km
* D to A: 7 km (via the distribution hub)
Total distance traveled = 12 + 4 + 12 + 7 = 35 km.
This question was withdrawn from the examination. The reason for withdrawal is that if the route sequence is CBDA, the vendor would travel from B to A (making D the final visited city, not A).
Q. 2 If the total number of widgets delivered in a day is 250 units, then what is the total distance covered in the route (in km)?
Check Solution
Ans: 38
Key considerations for route planning:
1. The journey commences at the distribution center and concludes at a designated point after visiting every required stop precisely one time.
2. When formulating the travel plan, the delivery agent prioritizes destinations based on their demand size, from highest to lowest. In cases of identical demand, the closest destination is visited first.
3. During route construction, the agent may opt for a direct connection between stops (if feasible) or a route passing through the distribution center, selecting the option that minimizes travel distance.
In the scenario presented, the total quantity of items delivered amounts to 250 units.
The maximum potential delivery capacity across all locations is calculated as: 70 units (Location A) + 50 units (Location D) + 60 units (Location B) + 100 units (Location C) = 280 units.
This implies a reduction of 30 units from the maximum potential. Such a reduction is only possible if Location C’s requirement is lowered to 70 units, as the combined difference for the other locations is 20 units.
Consequently, the sole feasible distribution is: 70 units (Location A) + 50 units (Location D) + 60 units (Location B) + 70 units (Location C).
Based on the first guideline, the sequence of visits is A – C – B – D (given that Location A is closer to the distribution center than Location C).
The distances are as follows:
– Distribution Center to Location A: 5 km
– Location A to Location C: 17 km
– Location C to Location B: 4 km
– Location B to Location D: 12 km
The total distance traveled is: 5 + 17 + 4 + 12 = 38 km.
Q. 3 What is the chance that the total number of widgets delivered in a day is 260 units and the route ends at Bikrampore?
Check Solution
Ans: D
The highest daily delivery capacity across all locations is the sum of individual maximums: 100 (C) + 70 (A) + 60 (B) + 50 (D), totaling 280 units.
The actual total delivered is 260 units, meaning there’s a shortfall of 20 units from the maximum possible delivery. This reduction of 20 units must come from one of the locations.
Location capacities are: A (70), B (60), C (100), and D (50).
The 20-unit reduction can be applied to A, B, or D.
Location C has a demand of 100 units, and it’s stated that the supplier’s first stop is C.
The route concludes at B.
The sequence begins as: C (100 units), …, …, B.
Considering B’s initial potential demand of 60 units, if the 20-unit reduction were not applied to B, its demand would need to be higher than 60 units to satisfy other constraints, which is not feasible given its capacity. Therefore, B’s demand must be 40 units.
This implies the 20-unit reduction occurred at location B. Consequently, the demand at location A remains 70 units, and the demand at location D becomes 50 units.
The delivery sequence is thus established as: C (100 units) -> A (70 units) -> D (50 units) -> B (40 units).
The fulfillment percentages for each location are:
C: 100 units (70%)
A: 70 units (60%)
D: 50 units (60%)
B: 40 units (30%)
The overall fulfillment percentage is calculated as the product of these percentages: 0.7 * 0.6 * 0.6 * 0.3 = 0.0756, which equals 7.56%.
The correct answer is option D.
Q. 4 If the first location visited from the warehouse is Ahmednagar, then what is the chance that the total distance covered in the route is 40 km?
Check Solution
Ans: A
It is stated that the initial destination from the depot is A.
If the requirement at A is 50 units, then the requirement at C must be less than 50 units, which is not feasible. Consequently, the requirement for locations A and C is determined to be 70 units each.
A (70 units) -> C (70 units)
Route from Warehouse to A: 5 km
Route from A to C: 17 km
Total distance traversed: 5 + 17 = 22 km
Uncovered distance: 40 – 22 = 18 km
Scenario 1:
Route from C to B: 4 km
Route from B to D: 12 km
Distance covered in this segment: 4 + 12 = 16 km, which is not equal to the remaining 18 km.
Scenario 2:
Route from C to D: 6 km
Route from D to B: 12 km
Distance covered in this segment: 6 + 12 = 18 km
This indicates that the supplier can cover the remaining 18 km by visiting D before B. This implies that the requirement at D should be greater than the requirement at B. This condition is met when D has a requirement of 50 units and B has a requirement of 40 units.
Given information:
D: 50 units with a 60% probability
B: 40 units with a 30% probability
The required value is calculated as the product of these probabilities:
0.6 * 0.3 = 0.18 = 18%
The correct option is A.
Q. 5 If Ahmednagar is not the first location to be visited in a route and the total route distance is 29 km, then which of the following is a possible number of widgets delivered on that day?
Check Solution
Ans: A
Key considerations for route planning:
1. The journey commences at the central depot and concludes at a final destination, having visited every specified point precisely once.
2. During route optimization, the supplier prioritizes locations based on demand, proceeding from highest to lowest. In instances of identical demand, proximity to the current location dictates the sequence.
3. When charting the course, the supplier can opt for a direct connection between two points, if such a route exists, or travel via the central depot. The path chosen will be the one covering the shortest distance.
Regarding demand:
All locations, except potentially the first one visited, must have a demand less than or equal to that of the initial location. The problem states that A cannot be the first location, and B and D are also excluded as starting points. This logically designates C as the first location to be visited.
Given the total travel distance is 29 km, and the distance from the central depot to C is 12 km.
This leaves 29 km – 12 km = 17 km for the remainder of the journey.
This remaining distance is achieved when C subsequently visits B, A, and D in that order, covering distances of 4 km, 6 km, and 7 km respectively (4 + 6 + 7 = 17 km).
Therefore, the optimal sequence is C – B – A – D.
The corresponding demands would be:
C: 70 or 100 units
B: 60 units
A: 50 units
D: 30 or 50 units
The potential total quantities of widgets delivered are:
Scenario 1: 70 (C) + 60 (B) + 50 (A) + 30 (D) = 210 units
Scenario 2: 70 (C) + 60 (B) + 50 (A) + 50 (D) = 230 units
Scenario 3: 100 (C) + 60 (B) + 50 (A) + 30 (D) = 240 units
Scenario 4: 100 (C) + 60 (B) + 50 (A) + 50 (D) = 260 units
The solution corresponds to option A.
Q. 6 Instructions
A new airlines company is planning to start operations in a country. The company has identified ten different cities which they plan to connect through their network to start with. The flight duration between any pair of cities will be less than one hour. To start operations, the company has to decide on a daily schedule.
The underlying principle that they are working on is the following:
Any person staying in any of these 10 cities should be able to make a trip to any other city in the morning and should be able to return by the evening of the same day.
If the underlying principle is to be satisfied in such a way that the journey between any two cities can be performed using only direct (non-stop) flights, then the minimum number of direct flights to be scheduled is:
Check Solution
Ans: C
There are ten distinct locations. The objective is to determine the smallest number of aerial journeys necessary to journey between any two of these locations. The number of unique pairs of locations that can be formed from ten is given by the combination formula, 10C2. For any selected pair of locations, say location X and location Y, a round trip would necessitate a minimum of four flights: one from X to Y, one from Y to X, one to return to X, and one to return to Y. Therefore, the total minimum number of required flights is calculated as the number of city pairs multiplied by four: 45 * 4 = 180.
Q. 7 Suppose three of the ten cities are to be developed as hubs. A hub is a city which is connected with every other city by direct flights each way, both in the morning as well as in the evening. The only direct flights which will be scheduled are originating and/or terminating in one of the hubs. Then the minimum number of direct flights that need to be scheduled so that the underlying principle of the airline to serve all the ten cities is met without visiting more than one hub during one trip is:
Check Solution
Ans: C
From each central point, there are departures and arrivals to 7 distinct locations. Therefore, the sum of flights commencing or concluding at any single central point amounts to 7 multiplied by 4, equaling 28. Across all three central points, this figure becomes 28 multiplied by 3, resulting in 84.
There are a total of three central points. These central points must also have direct connections between them. The aggregate number of flights connecting any pair of central points is 4. For the three central points, this amounts to 12.
Consequently, the final calculated value is 84 plus 12, which equals 96.
Q. 8 Suppose the 10 cities are divided into 4 distinct groups G1, G2, G3, G4 having 3, 3, 2 and 2 cities respectively and that G1 consists of cities named A, B and C. Further, suppose that direct flights are allowed only between two cities satisfying one of the following:
1. Both cities are in G1
2. Between A and any city in G2
3. Between B and any city in G3
4. Between C and any city in G4
Then the minimum number of direct flights that satisfies the underlying principle of the airline is:
Check Solution
Ans: 40
In Scenario 1 (G1), three distinct locations are designated as A, B, and C. Residents of any of these locations must have the opportunity for a round trip to any other location daily, with one trip occurring during daylight hours and another during nighttime hours. This necessitates a total of four travel routes connecting any two specific locations.
For instance, between location A and location B, the required routes are:
A to B (Daytime)
A to B (Nighttime)
B to A (Daytime)
B to A (Nighttime)
The total number of travel routes within the locations of G1 is calculated as the number of unique pairs of locations multiplied by the four routes per pair: (3 choose 2) * 4 = 3 * 4 = 12.
For travel routes between locations in Group A and any location in Group 2: 3 locations * 4 routes per location = 12 routes.
For travel routes between locations in Group B and any location in Group 3: 2 locations * 4 routes per location = 8 routes.
For travel routes between locations in Group C and any location in Group 4: 2 locations * 4 routes per location = 8 routes.
The aggregate sum of routes is (12 routes * 2 directions) + (8 routes * 2 directions) = 24 + 16 = 40.
Q. 9 Suppose the 10 cities are divided into 4 distinct groups Gl, G2, G3, G4 having 3, 3, 2 and 2 cities respectively and that Gl consists of cities named A, B and C. Further, suppose that direct flights are allowed only between two cities satisfying one of the following:
1. Both cities are in G1
2. Between A and any city in G2
3. Between B and any city in G3
4. Between C and any city in G4
However, due to operational difficulties at A, it was later decided that the only flights that would operate at A would be those to and from B. Cities in G2 would have to be assigned to G3 or to G4.
What would be the maximum reduction in the number of direct flights as compared to the situation before the operational difficulties arose?
Check Solution
Ans: 4
The cities originally in G2 will be reassigned to either G3 or G4. This reassignment will not alter the total number of flights originating from G1. The sole decrease in flight numbers will stem from the cessation of flights between A and C.
Therefore, the greatest possible decrease in direct flights from the initial operational state is 4.
Alternative approach:
Let’s calculate the number of flights under the revised conditions.
Flights connecting A and B = 4
Flights between B and any city within G3 = 4 * 4 = 16
Flights connecting C and B = 4
Flights between C and any city within G4 = 4 * 4 = 12
Consequently, the total number of flights = 36.
Thus, the reduction in flights = 40 – 36 = 4.
Q. 10 Instructions
Four cars need to travel from Akala (A) to Bakala (B). Two routes are available, one via Mamur (M) and the other via Nanur (N). The roads from A to M, and from N to B, are both short and narrow. In each case, one car takes 6 minutes to cover the distance, and each additional car increases the travel time per car by 3 minutes because of congestion. (For example, if only two cars drive from A to M, each car takes 9 minutes.) On the road from A to N, one car takes 20 minutes, and each additional car increases the travel time per car by 1 minute. On the road from M to B, one car takes 20 minutes, and each additional car increases the travel time per car by 0.9 minute.
The police department orders each car to take a particular route in such a manner that it is not possible for any car to reduce its travel time by not following the order, while the other cars are following the order.
How many cars would be asked to take the route A-N-B, that is Akala-Nanur-Bakala route, by the police department?
Check Solution
Ans: 2
Given the existence of two distinct paths, labeled A-M-B and A-N-B, and a total of four vehicles, an equitable distribution would allocate two vehicles to each path. Should a vehicle deviate from this allocation, its transit duration would be extended. Consider a scenario where three vehicles are permitted on the A-M-B route and only one on the A-N-B route. In this situation, a vehicle on the A-M-B route could potentially violate the designated distribution to shorten its journey. Therefore, the optimal and balanced approach necessitates permitting two vehicles on each path.
Q. 11 If all the cars follow the police order, what is the difference in travel time (in minutes) between a car which takes the route A-N-B and a car that takes the route A-M-B?
Check Solution
Ans: B
Since each route permits two vehicles, the travel durations for the A-M segment and the N-B segment will be identical. The variation in total travel time arises from the M-B segment and the A-N segment, with this difference amounting to 0.1 minutes. For the M-B route, a car will require 20 + 0.9 = 20.9 minutes. Conversely, for the A-N route, a car will need 20 + 1 = 21 minutes. Therefore, the disparity between these two times is 0.1 minutes.
Q. 12 A new one-way road is built from M to N. Each car now has three possible routes to travel from A to B: A-M-B, A-N-B and A-M-N-B. On the road from M to N, one car takes 7 minutes and each additional car increases the
travel time per car by 1 minute. Assume that any car taking the A-M-N-B route travels the A-M portion at the same time as other cars taking the A-M-B route, and the N-B portion at the same time as other cars taking the A-N-B route.
How many cars would the police department order to take the A-M-N-B route so that it is not possible for any car to reduce its travel time by not following the order while the other cars follow the order? (Assume that the police department would never order all the cars to take the same route.)
Check Solution
Ans: 2
Let’s explore different traffic distribution scenarios to find the most efficient travel times.
**Scenario 1:** Imagine 1 vehicle uses route AMB and 3 vehicles use route ANB.
* The travel time for AMB would be A to M plus M to B, totaling 6 + 20 = 26 minutes.
* The travel time for ANB would be A to N plus N to B, calculated as (20 + 2) + (6 + 3 * 2) = 34 minutes.
Now, consider if one vehicle originally assigned to ANB switches to AMB.
**Scenario 2:** Let’s consider a distribution where 2 vehicles take AMB and 2 vehicles take ANB.
* The travel time for AMB would be A to M plus M to B, calculated as (6 + 3) + (20 + 0.9) = 29.9 minutes.
* The travel time for ANB would be A to N plus N to B, calculated as (20 + 1) + (6 + 3) = 30 minutes.
In this case, if a vehicle switched from ANB to AMB (reducing its time from 34 to 29.9 minutes in Scenario 1’s logic), the initial assumption of Scenario 1 is not the most efficient, rendering it invalid.
Now, suppose one vehicle originally on ANB decides to switch to AMB.
**Scenario 3:** Assume 3 vehicles take AMB and 1 vehicle takes ANB.
* The travel time for AMB would be A to M plus M to B, calculated as (6 + 3 * 2) + (20 + 0.9 * 2) = 33.8 minutes.
* The travel time for ANB would be A to N plus N to B, calculated as (20) + (6) = 29 minutes.
Next, let’s consider if a vehicle on AMB switches to AMNB.
**Scenario 4:** Let’s distribute traffic with 2 vehicles on AMB, 1 vehicle on AMNB, and another on ANB.
* The travel time for AMB would be A to M plus M to B, calculated as (6 + 3 * 2) + (20 + 0.9) = 32.9 minutes.
* The travel time for AMNB would be A to M plus M to N plus N to B, calculated as (6 + 3 * 2) + (7) + (6 + 3) = 28 minutes.
* The travel time for ANB would be A to N plus N to B, calculated as (20) + (6 + 3) = 29 minutes.
The logic here is that if a vehicle (referred to as C) reduced its travel time from 33.8 minutes (in Scenario 3’s AMB) to 28 minutes (by switching to AMNB in Scenario 4), then Scenario 3 is not optimal and is therefore invalid.
Furthermore, if a vehicle (referred to as B) reduced its time from 30 minutes (in Scenario 2’s ANB) to 28 minutes (by switching routes), then Scenario 2 is also invalid.
Now, let’s see if a vehicle on AMB switching to AMNB improves things.
**Scenario 5:** Assume 1 vehicle takes AMB, 2 vehicles take AMNB, and another takes ANB.
In this setup:
* The segment A to M would be used by 3 vehicles.
* The segment M to B would be used by 1 vehicle.
* The segment M to N would be used by 2 vehicles.
* The segment A to N would be used by 1 vehicle.
* The segment N to B would be used by 3 vehicles.
Let’s calculate the travel times:
* The travel time for AMB would be A to M plus M to B, calculated as (6 + 3 * 2) + (20) = 32 minutes.
* The travel time for AMNB would be A to M plus M to N plus N to B, calculated as (6 + 3 * 2) + (7 + 1) + (6 + 3 * 2) = 32 minutes.
* The travel time for ANB would be A to N plus N to B, calculated as (20) + (6 + 3 * 2) = 32 minutes.
It’s evident that if a vehicle (referred to as D) switched from its previous route (resulting in 32.9 minutes in Scenario 4) to a new path that now takes 32 minutes, Scenario 4 is rendered invalid.
With this arrangement in Scenario 5, no vehicle can decrease its travel time by altering its path.
Therefore, the optimal distribution involves directing 2 vehicles onto the A-M-N-B route.
Q. 13 A new one-way road is built from M to N. Each car now has three possible routes to travel from A to B: A-M-B, A-N-B and A-M-N-B. On the road from M to N, one car takes 7 minutes and each additional car increases the travel time per car by j. minute. Assume that any car taking the A-M-N-B route travels the A-M portion at the same time as other cars taking the A-M-B route, and the N-B portion at the same time as other cars taking the A-N-B route.
If all the cars follow the police order, what is the minimum travel time (in minutes) from A to B? (Assume that the police department would never order all the cars to take the same route.)
Check Solution
Ans: B
Based on the preceding query, it was determined that:
– One vehicle utilizes the AMB path.
– Two vehicles opt for the AMNB path.
– The remaining vehicle selects the ANB path.
Consequently, the segment A-M is traversed by three vehicles, M-B by one vehicle, M-N by two vehicles, A-N by one vehicle, and N-B by three vehicles.
The transit duration for the AMB route is calculated as: A-M + M-B = (6 + 3 * 2) + (20) = 32 minutes.
The transit duration for the AMNB route is calculated as: A-M + M-N + N-B = (6 + 3 * 2) + (7 + 1) + (6 + 3 * 2) = 32 minutes.
The transit duration for the ANB route is calculated as: A-N + N-B = (20) + (6 + 3 * 2) = 32 minutes.
The shortest possible travel time from point A to point B is 32 minutes.